/LMAR=50/TMAR=50/RMAR=4095/BMAR=1/PMAR=0/XLINE=0/FONT#0=NGR13/USETI=0000096*TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX*

␈β	←␈↓ α6␈εαSECTION␈α4.4␈αof␈αTHE␈αAR␈α⎇T␈αOF␈αCOMPUTER␈αPR␈α␈OGRAMMING
␈β

␈↓ β%␈ε⊗⎇␈εα␈α1978␈αAddison↑Wesley␈αPublishing␈αCompan␈α␈y,␈αInc.
␈β⊃L␈↓ ε2␈ε∧0
␈β∪(

␈β↓Y␈↓ ↓H␈εα4.4␈ε∞␈↓ λ~R␈α↓A␈α␈DIX␈α	CONV␈α␈ERSION␈↓ 
v␈εα299
␈βα(␈↓ ↓H␈ε≥4␈α␈.4.␈α
R␈α↓ADIX␈α
CONVERSION
␈βαo␈↓ ↓H␈εαI␈↓ ∧
␈εαhad␈αin␈α␈v␈α␈en␈α␈ted␈αarithmetic␈αby␈αcoun␈α␈ting␈αwith␈αtheir␈αt␈α␈w␈α␈o␈α|sts␈αor
␈βαt␈↓ ↓T␈ε∧F␈α
OUR␈α
ANC␈α␈E␈α↓STORS
␈ββ~␈↓ ↓H␈εαtheir␈α
eigh␈α␈t␈α∞|ngers,␈α∞instead␈α
of␈α∞their␈α
ten␈α∞\digits,"␈α∞w␈α␈e␈α
w␈α␈ould␈α∞nev␈α␈er␈α
hav␈α␈e␈α∞to␈α
w␈α␈orry
␈ββE␈↓ ↓H␈εαabout␈α
writing␈αbinary-decimal␈αcon␈α␈v␈α␈ersion␈αroutines.␈α(And␈αw␈α␈e␈αw␈α␈ould␈αperhaps␈α
nev␈α␈er
␈ββp␈↓ ↓H␈εαhav␈α␈e␈α
learned␈α∞as␈α∞m␈α␈uch␈α
about␈α∞n␈α␈um␈α␈ber␈α∞systems.)␈α⊃In␈α
this␈α∞section,␈α∞w␈α␈e␈α∞shall␈α
discuss
␈β∧≠␈↓ ↓H␈εαthe␈α	con␈α␈v␈α␈ersion␈α	of␈α	n␈α␈um␈α␈bers␈α	from␈α	positional␈α	notation␈α	with␈α	one␈α	radix␈α	in␈α␈to␈α	positional
␈β∧G␈↓ ↓H␈εαnotation␈α
with␈α
another␈α
radix;␈αthis␈α
process␈α
is,␈αof␈α
course,␈αmost␈α
importan␈α␈t␈α
on␈α
binary
␈β∧r␈↓ ↓H␈εαcomputers␈α
when␈α
con␈α␈v␈α␈erting␈α
decimal␈α
input␈α
data␈α
in␈α␈to␈αbinary␈α
form,␈α
and␈α
con␈α␈v␈α␈erting
␈β¬≥␈↓ ↓H␈εαbinary␈αansw␈α␈ers␈αin␈α␈to␈αdecimal␈αform.
␈β¬h␈↓ ↓H␈ε∩A.␈απThe␈απfour␈απbasic␈απmethods.␈εα␈α∞Binary-decimal␈απcon␈α␈v␈α␈ersion␈απis␈αλone␈απof␈απthe␈απmost␈απmachine-
␈βε∪␈↓ ↓H␈εαdependen␈α␈t␈α⊃operations␈α⊃of␈α∩all,␈α∩since␈α∩engineers␈α⊃k␈α␈eep␈α⊃in␈α␈v␈α␈en␈α␈ting␈α∩di{eren␈α␈t␈α⊃ways␈α⊃to
␈βε>␈↓ ↓H␈εαpro␈α␈vide␈α∂for␈α⊂it␈α∂in␈α⊂the␈α∂computer␈α⊂hardware.␈α⊗Therefore␈α∂w␈α␈e␈α⊂shall␈α∂discuss␈α⊂only␈α∂the
␈βεj␈↓ ↓H␈εαgeneral␈α
principles␈α
in␈α␈v␈α␈olv␈α␈ed,␈α
from␈α
which␈α
a␈α
programmer␈α
can␈α
select␈αthe␈α
procedure
␈βπ∃␈↓ ↓H␈εαmost␈αw␈α␈ell␈αsuited␈αto␈αhis␈αmachine.
␈βπB␈↓ α␈εαWe␈α
shall␈α
assume␈α
that␈α
only␈α
nonnegativ␈α␈e␈α
n␈α␈um␈α␈bers␈α
en␈α␈ter␈α
in␈α␈to␈α
the␈αcon␈α␈v␈α␈ersion,
␈βπm␈↓ ↓H␈εαsince␈αthe␈αmanipulation␈αof␈αsigns␈αis␈αeasily␈αaccoun␈α␈ted␈αfor.
␈βλ→␈↓ α␈εαLet␈α
us␈α
assume␈α
that␈α
w␈α␈e␈α
are␈α
con␈α␈v␈α␈erting␈α
from␈α
radix␈↓ λ	␈ελb␈↓ λ!␈εαto␈α
radix␈↓ 	'␈ελB␈↓ 	?␈εα.␈α(The␈α
methods
␈βλE␈↓ ↓H␈εαcan␈αalso␈α
be␈αgeneralized␈αto␈αmix␈α␈ed-radix␈αnotations,␈αas␈αsho␈α␈wn␈αin␈αex␈α␈ercises␈α1␈αand␈α
2.)
␈βλp␈↓ ↓H␈εαMost␈α∞radix-con␈α␈v␈α␈ersion␈α
routines␈α∞are␈α∞based␈α∞on␈α∞m␈α␈ultiplication␈α∞and␈α∞division,␈α∞using
␈β	≠␈↓ ↓H␈εαone␈αof␈αthe␈αfollo␈α␈wing␈αfour␈αschemes:
␈β	f␈↓ α␈εα1)␈αCon␈α␈v␈α␈ersion␈αof␈αin␈α␈tegers␈α(radix␈αpoin␈α␈t␈αat␈αthe␈αrigh␈α␈t).
␈β
1␈↓ ↓H␈ε⊗∂␈εα␈α	Method␈α	(1a)␈ε∂␈α	Division␈α	by␈↓ ∧e␈ελB␈↓ ¬ε␈εα(using␈α
radix-␈↓ εL␈ελb␈↓ εc␈εαarithmetic).␈α∩Giv␈α␈en␈α	an␈α	in␈α␈teger␈α	n␈α␈um␈α␈ber
␈β
\␈↓ ↓H␈ελu␈↓ ↓]␈εα,␈αw␈α␈e␈αobtain␈αits␈αradix-␈↓ ∧(␈ελB␈↓ ∧M␈εαrepresen␈α␈tation␈α(␈↓ εD␈ελU␈↓ ε}␈εα.␈αε.␈αε.␈↓ π.␈ελU␈↓ πT␈ελU␈↓ πy␈εα)␈↓ λ%␈εαas␈αfollo␈α␈ws:
␈β
j␈↓ ε[␈εM␈↓ πE␈ε¬1␈↓ πk␈ε¬0␈↓ λ¬␈εB
␈β1␈↓ ¬λ␈ελU␈↓ ¬8␈εα=␈↓ ¬f␈ελu␈↓ ε↓␈εαmod␈↓ εK␈ελB
␈β?␈↓ ¬∨␈ε¬0
␈βd␈↓ ¬λ␈ελU␈↓ ¬8␈εα=␈ε⊗␈α
b␈↓ ¬t␈ελu␈↓ ε	␈εα/␈↓ ε≠␈ελB␈↓ ε4␈ε⊗c␈↓ εH␈εαmod␈↓ π∩␈ελB
␈βq␈↓ ¬∨␈ε¬1
␈β⊗␈↓ ¬λ␈ελU␈↓ ¬8␈εα=␈ε⊗␈α
bb␈↓ εα␈ελu␈↓ ε↔␈εα/␈↓ ε)␈ελB␈↓ εB␈ε⊗c␈εα/␈↓ εb␈ελB␈↓ εz␈ε⊗c␈↓ π∞␈εαmod␈↓ πX␈ελB
␈β$␈↓ ¬∨␈ε¬2
␈βI␈↓ ¬∧␈εα.␈αε.␈αε.
␈β
↔␈↓ ↓H␈εαetc.,␈αstopping␈αwhen␈ε⊗␈αb␈↓ ∧~␈εα.␈αε.␈αε.␈↓ ∧J␈ε⊗bb␈↓ ∧f␈ελu␈↓ ∧{␈εα/␈↓ ¬
␈ελB␈↓ ¬&␈ε⊗c␈εα/␈↓ ¬F␈ελB␈↓ ¬↑␈ε⊗c␈↓ ¬r␈εα.␈αε.␈αε.␈↓ ε"␈εα/␈↓ ε4␈ελB␈↓ εL␈ε⊗c␈εα␈α
=␈α
0.
␈β
b␈↓ ↓H␈ε⊗∂␈εα␈α	Method␈α
(1b)␈ε∂␈α
Multiplication␈α
by␈↓ ¬H␈ελb␈↓ ¬`␈εα(using␈α
radix-␈↓ π&␈ελB␈↓ πH␈εαarithmetic).␈α∀If␈↓ 	5␈ελu␈↓ 	U␈εαhas␈α
the␈α	radix-
␈β∞
␈↓ ↓H␈ελb␈↓ ↓f␈εαrepresen␈α␈tation␈α⊂(␈↓ βa␈ελu␈↓ ∧∃␈εα.␈αε.␈αε.␈↓ ∧E␈ελu␈↓ ∧h␈ελu␈↓ ¬␈εα)␈↓ ¬#␈εα,␈α⊃w␈α␈e␈α⊂can␈α⊂use␈α⊂radix-␈↓ π]␈ελB␈↓ λ¬␈εαarithmetic␈α⊂to␈α⊂evaluate␈α∂the
␈β∞~␈↓ βu␈εm␈↓ ∧Z␈ε¬1␈↓ ∧⎇␈ε¬0␈↓ ¬↔␈εb
␈β∞3␈↓ β>␈εm
␈β∞8␈↓ ↓H␈εαpolynomial␈↓ βα␈ελu␈↓ β0␈ελb␈↓ β`␈εα+␈↓ ∧␈ε⊗↓␈αε↓␈αε↓␈↓ ∧>␈εα+␈↓ ∧j␈ελu␈↓ ¬
␈ελb␈↓ ¬$␈εα+␈↓ ¬P␈ελu␈↓ ¬⎇␈εα=␈↓ ε+␈ελu␈↓ εL␈εαin␈αthe␈αform
␈β∞F␈↓ β⊗␈εm␈↓ ∧␈␈ε¬1␈↓ ¬d␈ε¬0
␈β∞s␈↓ βe␈ε↓␈␈↓ λ␈ε↓↓
␈β∂∪␈↓ βs␈εα(␈↓ ∧¬␈εα.␈αε.␈αε.␈↓ ∧5␈εα(␈↓ ∧A␈ελu␈↓ ∧t␈ελb␈↓ ¬␈εα+␈↓ ¬7␈ελu␈↓ ε⊂␈εα)␈↓ ε"␈ελb␈↓ ε9␈εα+␈↓ εe␈ε⊗↓␈αε↓␈αε↓␈↓ π∃␈εα)␈↓ π'␈ελb␈↓ π=␈εα+␈↓ πi␈ελu␈↓ λ ␈ελb␈↓ λ6␈εα+␈↓ λb␈ελu␈↓ 	¬␈εα.
␈β∂ ␈↓ ∧U␈εm␈↓ ¬K␈εm␈↓ ¬e␈ε→␈␈ε¬1␈↓ π⎇␈ε¬1␈↓ λw␈ε¬0
␈β∂o␈↓ α␈εα2)␈α∂Con␈α␈v␈α␈ersion␈α∂of␈α∂fractions␈α∂(radix␈α∂poin␈α␈t␈α∂at␈α∂the␈α⊂left).␈α≡Note␈α∂that␈α∂it␈α∂is␈α∂often
␈β⊂~␈↓ ↓H␈εαimpossible␈α	to␈α
express␈α
a␈α	terminating␈α
radix-␈↓ εT␈ελb␈↓ εl␈εαfraction␈α
(0.␈↓ λ_␈ελu␈↓ λX␈ελu␈↓ 	≥␈εα.␈αε.␈αε.␈↓ 	M␈ελu␈↓ 
→␈εα)␈↓ 
:␈ε∂exactly
␈β⊂(␈↓ λ,␈ε→␈␈ε¬1␈↓ λl␈ε→␈␈ε¬2␈↓ 	b␈ε→␈␈↓ 	␈␈εm␈↓ 
%␈εb
␈β⊂F␈↓ ↓H␈εαas␈αa␈αterminating␈αradix-␈↓ ∧4␈ελB␈↓ ∧Y␈εαfraction␈α(0.␈↓ επ␈ελU␈↓ εI␈ελU␈↓ π∩␈εα.␈αε.␈αε.␈↓ πB␈ελU␈↓ λ∪␈εα)␈↓ λ3␈εα.␈α
For␈αexample,␈αthe␈αfrac-
␈β⊂S␈↓ ε≡␈ε→␈␈ε¬1␈↓ ε`␈ε→␈␈ε¬2␈↓ πY␈ε→␈␈↓ πu␈εM␈↓ λ∨␈εB
␈β⊂n␈↓ α ␈ε¬1
␈β⊂q␈↓ ↓H␈εαtion␈↓ αH␈εαhas␈α∂the␈α∂in|nite␈α∂binary␈α∂represen␈α␈tation␈α∞(0.0001100110011...␈↓ 	[␈εα)␈↓ 	v␈εα.␈α∀Therefore
␈β⊂}␈↓ 	g␈ε¬2
␈β⊃↓␈↓ α→␈∧⊃↓α→α≥
␈β⊃∧␈↓ α→␈ε¬10
␈β⊃≤␈↓ ↓H␈εαmethods␈αof␈αrounding␈αthe␈αresult␈αto␈↓ ¬h␈ελM␈↓ ε→␈εαplaces␈αare␈αsometimes␈αof␈αin␈α␈terest.
␈β∪(

␈β↓Y␈↓ ↓H␈εα300␈↓ α=␈ε∞A␈α␈RITH␈α␈METIC␈εα␈↓ 
}4.4
␈βα&␈↓ ↓H␈ε⊗∂␈εα␈α
Method␈α
(2a)␈ε∂␈α
Multiplication␈α
by␈↓ ¬F␈ελB␈↓ ¬h␈εα(using␈α
radix-␈↓ π.␈ελb␈↓ πG␈εαarithmetic).␈α∀Giv␈α␈en␈α
a␈α
fractional
␈βαQ␈↓ ↓H␈εαn␈α␈um␈α␈ber␈↓ αE␈ελu␈↓ αZ␈εα,␈αλw␈α␈e␈αλobtain␈απsuccessiv␈α␈e␈απdigits␈απof␈απits␈απradix-␈↓ π7␈ελB␈↓ πV␈εαrepresen␈α␈tation␈απ(.␈↓ 	R␈ελU␈↓ 
∃␈ελU␈↓ 
]␈εα.␈αε.␈αε.␈↓ 
␈εα)
␈βα←␈↓ 	i␈ε→␈␈ε¬1␈↓ 
,␈ε→␈␈ε¬␈α␈2␈↓ →␈εB
␈βα⎇␈↓ ↓H␈εαas␈αfollo␈α␈ws:
␈ββ≠␈↓ ¬≤␈ελU␈↓ ¬h␈εα=␈ε⊗␈α
b␈↓ ε$␈ελu␈↓ ε:␈ελB␈↓ εR␈ε⊗c
␈ββ)␈↓ ¬3␈ε→␈␈ε¬1
␈ββN␈↓ ¬≤␈ελU␈↓ ¬h␈εα=␈ε⊗␈α
bf␈↓ ε6␈ελu␈↓ εL␈ελB␈↓ εd␈ε⊗g␈↓ εv␈ελB␈↓ π∞␈ε⊗c
␈ββ[␈↓ ¬3␈ε→␈␈ε¬2
␈β∧␈↓ ¬≤␈ελU␈↓ ¬h␈εα=␈ε⊗␈α
bff␈↓ εH␈ελu␈↓ ε↑␈ελB␈↓ εv␈ε⊗g␈↓ πλ␈ελB␈↓ π ␈ε⊗g␈↓ π2␈ελB␈↓ πJ␈ε⊗c
␈β∧
␈↓ ¬3␈ε→␈␈ε¬3
␈β∧2␈↓ ¬4␈εα.␈αε.␈αε.
␈β∧f␈↓ ↓H␈εαwhere␈ε⊗␈α
f␈↓ αC␈ελx␈↓ αU␈ε⊗g␈εα␈α
denotes␈↓ βw␈ελx␈↓ ∧⊂␈εαmod␈↓ ∧Z␈εα1␈α=␈↓ ¬'␈ελx␈↓ ¬B␈ε⊗␈␈α	b␈↓ ¬⎇␈ελx␈↓ ε⊂␈ε⊗c␈εα.␈α∂If␈αit␈α
is␈α
desired␈α
to␈α
round␈α
the␈α
result␈α
to␈↓ π␈ελM
␈β¬∩␈↓ ↓H␈εαplaces,␈α	the␈αλcomputation␈αλcan␈α	be␈αλstopped␈αλafter␈↓ π↓␈ελU␈↓ π[␈εαhas␈αλbeen␈αλcalculated,␈α	and␈↓ 
[␈ελU
␈β¬∨␈↓ π_␈ε→␈␈↓ π4␈εM␈↓ 
r␈ε→␈␈↓ ∂␈εM
␈β¬:␈↓ 
↔␈ε¬1
␈β¬=␈↓ ↓H␈εαshould␈α∂be␈α⊂increased␈α∂by␈α⊂unity␈α∂if␈ε⊗␈α⊂f␈↓ ¬i␈εα.␈αε.␈αε.␈↓ ε→␈ε⊗ff␈↓ ε=␈ελn␈↓ εS␈ελB␈↓ εk␈ε⊗g␈↓ ε⎇␈ελB␈↓ π∃␈ε⊗g␈↓ π-␈εα.␈αε.␈αε.␈↓ π]␈ελB␈↓ πu␈ε⊗g␈εα␈α⊂is␈α∂greater␈α⊂than␈↓ 
*␈εα.␈α⊗(Note,
␈β¬M␈↓ 
↔␈∧¬M
↔α∂
␈β¬P␈↓ 
↔␈ε¬2
␈β¬h␈↓ ↓H␈εαho␈α␈w␈α␈ev␈α␈er,␈α⊂that␈α∂this␈α⊂may␈α∂cause␈α⊂carries␈α∂to␈α∂propagate,␈α⊃and␈α∂these␈α⊂carries␈α∂m␈α␈ust␈α∂be
␈βε∪␈↓ ↓H␈εαincorporated␈αλin␈α␈to␈α	the␈αλansw␈α␈er␈α	using␈α	radix-␈↓ εC␈ελB␈↓ εd␈εαarithmetic.␈α
It␈α	w␈α␈ould␈α	be␈αλsimpler␈α	to␈αλadd
␈βε9␈↓ βF␈ε→␈␈↓ βc␈εM
␈βε;␈↓ β≠␈ε¬1
␈βε>␈↓ ↓H␈εαthe␈αconstan␈α␈t␈↓ β.␈ελB␈↓ ∧
␈εαto␈αthe␈αoriginal␈αn␈α␈um␈α␈ber␈↓ ε|␈ελu␈↓ π≥␈εαbefore␈α
the␈αcalculation␈αbegins,␈αbut
␈βεO␈↓ β≠␈∧εOβ≠α∂
␈βεQ␈↓ β≠␈ε¬2
␈βεe␈↓ λ
␈ε→␈␈↓ λ*␈εM
␈βεf␈↓ πc␈ε¬1
␈βεj␈↓ ↓H␈εαthis␈αmay␈αlead␈αto␈αa␈αterribly␈αincorrect␈αansw␈α␈er␈αwhen␈↓ πu␈ελB␈↓ λT␈εαcannot␈αbe␈αrepresen␈α␈ted
␈βεz␈↓ πc␈∧εzπcα∂
␈βε|␈↓ πc␈ε¬2
␈βπ∃␈↓ ↓H␈εαexactly␈αas␈α
a␈αradix-␈↓ βj␈ελb␈↓ ∧∧␈εαn␈α␈um␈α␈ber␈α
inside␈αthe␈αcomputer.␈αNote␈αfurther␈αthat␈αit␈αis␈α
possible
␈βπ;␈↓ π#␈εm␈↓ λ∨␈εM
␈βπ@␈↓ ↓H␈εαfor␈αthe␈αansw␈α␈er␈αto␈αround␈αup␈αto␈α(1.00␈↓ ¬{␈εα.␈αε.␈αε.␈↓ ε+␈εα0␈↓ ε=␈εα)␈↓ ε\␈εα,␈αif␈↓ π∀␈ελb␈↓ πF␈ε⊗∃␈εα␈α
2␈↓ λε␈ελB␈↓ λ=␈εα.)
␈βπM␈↓ εI␈εB
␈βπk␈↓ α␈εαEx␈α␈ercise␈α
3␈α
sho␈α␈ws␈α	ho␈α␈w␈α
to␈α
extend␈α
this␈α
method␈α
so␈α	that␈↓ λ7␈ελM␈↓ λg␈εαis␈ε∂␈α	variable␈εα,␈αjust␈α	large
␈βλ⊗␈↓ ↓H␈εαenough␈αto␈αrepresen␈α␈t␈αthe␈αoriginal␈αn␈α␈um␈α␈ber␈αto␈αa␈αspeci|ed␈αaccuracy;␈αin␈αthis␈αcase␈αthe
␈βλB␈↓ ↓H␈εαproblem␈αof␈αcarries␈αdoes␈αnot␈αoccur.
␈βλ␈␈↓ ↓H␈ε⊗∂␈εα␈α∂Method␈α∂(2b)␈ε∂␈α⊂Division␈α∂by␈↓ ¬π␈ελb␈↓ ¬$␈εα(using␈α⊂radix-␈↓ εp␈ελB␈↓ π↔␈εαarithmetic).␈α If␈↓ 	⊗␈ελu␈↓ 	;␈εαhas␈α⊂the␈α∂radix-␈↓ ≡␈ελb
␈β	*␈↓ ↓H␈εαrepresen␈α␈tation␈α
(0.␈↓ β\␈ελu␈↓ ∧≤␈ελu␈↓ ∧b␈εα.␈αε.␈αε.␈↓ ¬∩␈ελu␈↓ ¬]␈εα)␈↓ ¬u␈εα,␈α∞w␈α␈e␈α∞can␈α∞use␈α
radix-␈↓ λ%␈ελB␈↓ λK␈εαarithmetic␈α∞to␈α
evaluate
␈β	7␈↓ βq␈ε→␈␈ε¬1␈↓ ∧1␈ε→␈␈ε¬␈α␈2␈↓ ¬&␈ε→␈␈↓ ¬C␈εm␈↓ ¬i␈εb
␈β	P␈↓ α⊗␈ε→␈␈ε¬1␈↓ βC␈ε→␈␈ε¬2␈↓ ¬Z␈ε→␈␈↓ ¬w␈εm
␈β	U␈↓ ↓H␈ελu␈↓ απ␈ελb␈↓ αI␈εα+␈↓ αu␈ελu␈↓ β5␈ελb␈↓ βv␈εα+␈↓ ∧"␈ε⊗↓␈αε↓␈αε↓␈↓ ∧T␈εα+␈↓ ¬␈ελu␈↓ ¬L␈ελb␈↓ ε≥␈εαin␈αthe␈αform
␈β	b␈↓ ↓\␈ε→␈␈ε¬1␈↓ β
␈ε→␈␈ε¬␈α␈2␈↓ ¬∃␈ε→␈␈↓ ¬2␈εm
␈β
β␈↓ β$␈ε↓␈␈↓ 	_␈ε↓↓
␈β
#␈↓ β2␈εα(␈↓ βD␈εα.␈αε.␈αε.␈↓ βt␈εα(␈↓ ∧␈ελu␈↓ ∧K␈εα/␈↓ ∧]␈ελb␈↓ ∧t␈εα+␈↓ ¬ ␈ελu␈↓ ¬y␈εα)/␈↓ ε↔␈ελb␈↓ ε.␈εα+␈↓ εZ␈ε⊗↓␈αε↓␈αε↓␈↓ π␈εα+␈↓ π8␈ελu␈↓ πx␈εα)/␈↓ λ⊗␈ελb␈↓ λ,␈εα+␈↓ λX␈ελu␈↓ 	&␈εα/␈↓ 	8␈ελb␈↓ 	F␈εα.
␈β
0␈↓ ∧∃␈ε→␈␈↓ ∧1␈εm␈↓ ¬4␈ε¬1␈ε→␈α↓␈␈↓ ¬←␈εm␈↓ πL␈ε→␈␈ε¬2␈↓ λl␈ε→␈␈ε¬1
␈β
q␈↓ ↓H␈εαCare␈α∂should␈α∂be␈α∂tak␈α␈en␈α∂to␈α∂con␈α␈trol␈α∂errors␈α∂that␈α∂migh␈α␈t␈α∂occur␈α∂due␈α∂to␈α∂truncation␈α∂or
␈β≤␈↓ ↓H␈εαrounding␈αin␈αthe␈αdivision␈αby␈↓ ¬α␈ελb␈↓ ¬⊂␈εα;␈αthese␈αare␈αoften␈αnegligible,␈αbut␈αnot␈αalways.
␈βY␈↓ α␈εαTo␈α
summarize,␈α∞Methods␈α
(1a),␈α
(1b),␈α
(2a),␈α∞and␈α
(2b)␈α
giv␈α␈e␈α
us␈α
t␈α␈w␈α␈o␈α
choices␈α
for␈α
a
␈β∧␈↓ ↓H␈εαcon␈α␈v␈α␈ersion␈α
process,␈α
depending␈α
on␈α
whether␈αour␈α
n␈α␈um␈α␈ber␈α
is␈α
an␈α
in␈α␈teger␈α
or␈α
a␈α
fraction.
␈β/␈↓ ↓H␈εαAnd␈α
it␈αis␈α
certainly␈α
possible␈α
to␈α
con␈α␈v␈α␈ert␈α
bet␈α␈w␈α␈een␈α
in␈α␈tegers␈α
and␈α
fractions␈α
by␈αm␈α␈ulti-
␈βZ␈↓ ↓H␈εαplying␈α
or␈αdividing␈αby␈α
an␈αappropriate␈αpo␈α␈w␈α␈er␈α
of␈↓ π≥␈ελb␈↓ π6␈εαor␈↓ π`␈ελB␈↓ πy␈εα;␈αtherefore␈α
there␈αare␈αat␈α
least
␈β
¬␈↓ ↓H␈εαfour␈αmethods␈αto␈αchoose␈αfrom␈αwhen␈αtrying␈αto␈αdo␈αa␈αcon␈α␈v␈α␈ersion.
␈β
B␈↓ ↓H␈ε∩B.␈α
Single-precision␈α
con␈α␈v␈α␈ersion.␈εα␈α≠To␈α
illustrate␈α
these␈α
four␈α
methods,␈α
let␈α
us␈α
assume
␈β
n␈↓ ↓H␈εαthat␈ε∃␈α
MIX␈εα␈α
is␈α∞a␈α
binary␈α∞computer,␈α∞and␈α
suppose␈α∞that␈α
w␈α␈e␈α∞wan␈α␈t␈α∞to␈α
con␈α␈v␈α␈ert␈α∞a␈α
binary
␈β∞→␈↓ ↓H␈εαin␈α␈teger␈↓ α@␈ελu␈↓ αc␈εαto␈α
a␈α
decimal␈α∞in␈α␈teger.␈α∂Th␈α␈us␈↓ ε⊗␈ελb␈↓ ε0␈εα=␈α2␈α
and␈↓ πG␈ελB␈↓ πk␈εα=␈α10.␈α⊂Method␈α
(1a)␈α
could␈α
be
␈β∞D␈↓ ↓H␈εαprogrammed␈αas␈αfollo␈α␈ws:
␈β∂λ␈↓ β#␈ε∃EN␈α␈T1␈↓ ∧∨␈ε∃0
␈β∂␈↓ ε"␈εβS␈α␈et␈↓ ε[␈ε	j␈↓ εs␈ε↔ ␈εβ␈α
0␈α␈.
␈β∂/␈↓ β#␈ε∃LD␈α␈X␈↓ ∧∨␈ε∃U
␈β∂W␈↓ β#␈ε∃EN␈α␈TA␈↓ ∧∨␈ε∃0
␈β∂Z␈↓ ε"␈εβS␈α␈et␈↓ ε[␈εβrAX␈↓ π!␈ε↔ ␈↓ πL␈ε	u␈↓ π`␈εβ.
␈β∂␈␈↓ αP␈ε∃1H␈↓ β#␈ε∃DI␈α␈V␈↓ ∧∨␈ε∃=10␈α␈=
␈β⊂α␈↓ ε"␈εβ(␈↓ ε-␈εβrA␈↓ εR␈εβ,␈↓ ε`␈εβrX␈↓ π¬␈εβ)␈ε↔␈α
 ␈εβ␈α	(␈ε↔b␈↓ π\␈εβrAX␈↓ λ→␈εβ/10␈ε↔␈α␈c␈εβ,␈↓ λg␈εβrAX␈↓ 	*␈εβm␈α␈od␈↓ 	n␈εβ10␈α␈)␈α↓.
␈β⊂∪␈↓ α␈εα(1)
␈β⊂&␈↓ β#␈ε∃ST␈α␈X␈↓ ∧∨␈ε∃ANS␈α␈WER␈α␈,1
␈β⊂)␈↓ ε"␈ε	U␈↓ εL␈ε↔ ␈↓ εw␈εβrX␈↓ π≤␈εβ.
␈β⊂4␈↓ ε7␈εj
␈β⊂N␈↓ β#␈ε∃IN␈α␈C1␈↓ ∧∨␈ε∃1
␈β⊂Q␈↓ ε"␈ε	j␈↓ ε:␈ε↔ ␈↓ εd␈ε	j␈↓ ε{␈εβ+␈απ1.
␈β⊂u␈↓ β#␈ε∃SR␈α␈AX␈↓ ∧∨␈ε∃5
␈β⊂x␈↓ ε"␈εβr␈α␈A␈α↓X␈↓ εh␈ε↔ ␈↓ π∩␈εβrA␈↓ π7␈εβ.
␈β⊃≥␈↓ β#␈ε∃JX␈α␈P␈↓ ∧∨␈ε∃1B
␈β⊃ ␈↓ ε"␈εβRe␈α␈pea␈α␈t␈αun␈α}ti␈α↓l␈αresu␈α␈lt␈αi␈α↓s␈αze␈α␈ro.
␈β⊃"␈↓ 	I␈∧⊃"	I≠∂
␈β∪(

␈β↓Y␈↓ ↓H␈εα4.4␈ε∞␈↓ λ~R␈α↓A␈α␈DIX␈α	CONV␈α␈ERSION␈↓ 
v␈εα301
␈βα(␈↓ ↓H␈εαThis␈αrequires␈α18␈↓ βD␈ελM␈↓ βq␈εα+␈αλ4␈αcy␈α␈cles␈αto␈αobtain␈↓ ε>␈ελM␈↓ εp␈εαdigits.
␈βαS␈↓ α␈εαThe␈α
abo␈α␈v␈α␈e␈αmethod␈α
uses␈α
division␈αby␈α
10;␈α
Method␈α
(2a)␈αuses␈ε∂␈α
m␈α␈ultiplication␈εα␈αby
␈βα}␈↓ ↓H␈εα10,␈αso␈αit␈αmigh␈α␈t␈αbe␈αa␈αlittle␈αfaster.␈αIn␈αorder␈αto␈αuse␈αMethod␈α(2a),␈αw␈α␈e␈αm␈α␈ust␈αdeal␈αwith
␈ββ*␈↓ ↓H␈εαfractions,␈α
and␈α
this␈α
leads␈α
to␈α	an␈α
in␈α␈teresting␈α
situation.␈αLet␈↓ λ+␈ελw␈↓ λP␈εαbe␈α
the␈α
w␈α␈ord␈α
size␈α
of␈α	the
␈ββP␈↓ ¬w␈εn
␈ββU␈↓ ↓H␈εαcomputer,␈αand␈α
assume␈αthat␈↓ ¬∧␈ελu␈↓ ¬%␈εα<␈α
1␈↓ ¬e␈εα0␈↓ ε∀␈εα<␈↓ εC␈ελw␈↓ ε↑␈εα.␈α∞With␈αa␈α
single␈αdivision␈α
w␈α␈e␈αcan␈α
|nd␈↓ ≤␈ελq
␈β∧␈↓ ↓H␈εαand␈↓ α∞␈ελr␈↓ α≥␈εα,␈αwhere
␈β∧%␈↓ ¬9␈εn␈↓ λ,␈εn
␈β∧+␈↓ ∧,␈ελw␈↓ ∧G␈ελu␈↓ ∧g␈εα=␈α
1␈↓ ¬'␈εα0␈↓ ¬J␈ελq␈↓ ¬c␈εα+␈↓ ε∂␈ελr␈↓ ε≡␈εα,␈↓ εv0␈ε⊗␈α
∀␈↓ π@␈ελr␈↓ πZ␈εα<␈α
1␈↓ λ~␈εα0␈↓ λ>␈εα.␈↓ α␈εα(2)
␈β∧o␈↓ ↓H␈εαNo␈α␈w␈α
if␈αw␈α␈e␈αapply␈αMethod␈α(2a)␈αto␈αthe␈α
fraction␈α(␈↓ π∪␈ελq␈↓ π*␈εα+␈αε1)/␈↓ λ∧␈ελw␈↓ λ∨␈εα,␈αw␈α␈e␈αwill␈αobtain␈αthe␈α
digits
␈β¬~␈↓ ↓H␈εαof␈↓ ↓r␈ελu␈↓ α∪␈εαfrom␈αleft␈αto␈αrigh␈α␈t,␈αin␈↓ ∧`␈ελn␈↓ ¬α␈εαsteps,␈αsince
␈β¬g␈↓ π∃␈εn
␈β¬h␈↓ ∧≡␈ε↓⊗␈↓ ¬L␈ε↓↔␈↓ ε∀␈ε↓⊗␈↓ πo␈ε↓↔
␈β¬l␈↓ ∧q␈ελq␈↓ ¬
␈εα+␈αλ1␈↓ εq␈εα1␈↓ πβ␈εα0␈↓ π/␈ε⊗␈␈↓ π[␈ελr
␈β¬⎇␈↓ ∧R␈εn
␈βεβ␈↓ ∧.␈εα1␈↓ ∧@␈εα0␈↓ ¬f␈εα=␈↓ ε$␈ελu␈↓ εA␈εα+␈↓ λ	␈εα=␈↓ λ7␈ελu␈↓ λM␈εα.␈↓ α␈εα(3)
␈βε∪␈↓ ∧q␈∧ε∪∧qαW␈↓ εq␈∧ε∪εqαz
␈βε≠␈↓ ¬∂␈ελw␈↓ π!␈ελw
␈βεm␈↓ ↓H␈εα(This␈α
idea␈α∞is␈α∞due␈α∞to␈α∞P.␈α
A.␈α∞Samet,␈ε∂␈α∞Soft␈α␈ware←Practice␈α∞and␈α∞Experience␈ε∩␈α∞1␈εα␈α
(1971),
␈βπ_␈↓ ↓H␈εα93↑96.)
␈βπD␈↓ α␈εαHere␈αis␈αthe␈αcorresponding␈ε∃␈αMI␈α␈X␈εα␈αprogram:
␈βλ∞␈↓ αy␈ε∃JO␈α␈V␈↓ βu␈ε∃OFL␈α␈O
␈βλ⊃␈↓ ¬x␈εβEn␈α␈sure␈αo␈α}v␈α␈er⎇␈α␈o␈α␈w␈αis␈αo{.
␈βλ6␈↓ αy␈ε∃LD␈α␈A␈↓ βu␈ε∃U
␈βλ]␈↓ ∧+␈εn␈↓ πg␈εn
␈βλ↑␈↓ αy␈ε∃LD␈α␈X␈↓ βu␈ε∃=␈↓ ∧<␈ε∃=
␈βλa␈↓ ∧
␈εβ1␈↓ ∧≠␈εβ0␈↓ ¬x␈εβrAX␈↓ ε>␈ε↔ ␈↓ εh␈ε	w␈↓ π↓␈ε	u␈↓ π≥␈εβ+␈απ1␈↓ πV␈εβ0␈↓ πw␈εβ.
␈β	∧␈↓ ∧+␈εn
␈β	¬␈↓ αy␈ε∃DI␈α␈V␈↓ βu␈ε∃=␈↓ ∧<␈ε∃=
␈β	λ␈↓ ∧
␈εβ1␈↓ ∧≠␈εβ0␈↓ ¬x␈εβrA␈↓ ε&␈ε↔ ␈↓ εP␈ε	q␈↓ εg␈εβ+␈απ1,␈↓ π4␈εβrX␈↓ πb␈ε↔ ␈↓ λ
␈ε	r␈↓ λ≤␈εβ.
␈β	,␈↓ π]␈εn
␈β	-␈↓ αy␈ε∃JO␈α␈V␈↓ βu␈ε∃ERR␈α␈OR
␈β	0␈↓ ¬x␈εβJ␈α␈um␈α␈p␈αif␈↓ εt␈ε	u␈↓ π⊃␈ε↔∃␈εβ␈α	1␈↓ πL␈εβ0␈↓ πm␈εβ.
␈β	T␈↓ αy␈ε∃EN␈α␈T1␈↓ ∧	␈ε∃-1
␈β	U␈↓ α␈εα(4)
␈β	W␈↓ βu␈ε	n␈↓ ¬x␈εβS␈α␈et␈↓ ε1␈ε	j␈↓ εI␈ε↔ ␈↓ εt␈ε	n␈↓ π∂␈ε↔␈␈εβ␈αλ1␈α␈.
␈β	|␈↓ α&␈ε∃2H␈↓ αy␈ε∃MU␈α␈L␈↓ βu␈ε∃=10␈α␈=
␈β	␈␈↓ ¬x␈εβN␈α␈o␈α␈w␈αi␈α↓m␈α␈agin␈α␈e␈αrad␈α␈i␈α↓x␈α
po␈α␈i␈α↓n␈α}t␈αat␈αleft,␈↓ 	Z␈εβrA␈↓ 
	␈εβ=␈↓ 
3␈ε	x␈↓ 
E␈εβ.
␈β
$␈↓ αy␈ε∃ST␈α␈A␈↓ βu␈ε∃ANS␈α␈WER␈α␈,1
␈β
'␈↓ ¬x␈εβS␈α␈et␈↓ ε1␈ε	U␈↓ ε[␈ε↔ ␈α
b␈εβ10␈↓ π4␈ε	x␈↓ πF␈ε↔c␈εβ.
␈β
1␈↓ εF␈εj
␈β
K␈↓ αy␈ε∃SL␈α␈AX␈↓ βu␈ε∃5
␈β
N␈↓ ¬x␈ε	x␈↓ ε∩␈ε↔ ␈α
f␈εβ␈α␈10␈↓ εo␈ε	x␈↓ π␈ε↔g␈εβ.
␈β
s␈↓ αy␈ε∃DE␈α␈C1␈↓ βu␈ε∃1
␈β
v␈↓ ¬x␈ε	j␈↓ ε⊂␈ε↔ ␈↓ ε:␈ε	j␈↓ εQ␈ε↔␈␈εβ␈απ1.
␈β~␈↓ αy␈ε∃J1␈α␈NN␈↓ βu␈ε∃2B
␈β≥␈↓ ¬x␈εβRe␈α␈pea␈α␈t␈αfor␈↓ π≥␈ε	n␈↓ π:␈εβ>␈↓ πe␈ε	j␈↓ π⎇␈ε↔∃␈εβ␈α
0␈α␈.
␈β∨␈↓ λg␈∧∨λg≠∂
␈βg␈↓ ↓H␈εαThis␈αsligh␈α␈tly␈αlonger␈αroutine␈α
requires␈α16␈↓ ε,␈ελn␈↓ εJ␈εα+␈αλ19␈αcy␈α␈cles,␈αso␈αit␈α
is␈αa␈αlittle␈αfaster␈αthan
␈β∩␈↓ ↓H␈εαprogram␈α(1)␈αif␈↓ β0␈ελn␈↓ βO␈εα=␈↓ β⎇␈ελM␈↓ ∧-␈ε⊗∃␈εα␈α
8;␈αwhen␈αleading␈αzeros␈αare␈αpresen␈α␈t,␈α(1)␈αwill␈αbe␈αfaster.
␈β8␈↓ 
4␈εm
␈β=␈↓ α␈εαProgram␈α(4)␈α
as␈αit␈α
stands␈αcannot␈αbe␈α
used␈αto␈αcon␈α␈v␈α␈ert␈α
in␈α␈tegers␈↓ 	A␈ελu␈↓ 	b␈ε⊗∃␈εα␈α
1␈↓ 
"␈εα0␈↓ 
Z␈εαwhen
␈βd␈↓ ↓l␈εm␈↓ β?␈εm␈↓ βY␈ε¬+1
␈βi␈↓ ↓H␈εα1␈↓ ↓Z␈εα0␈↓ α∩␈εα<␈↓ αC␈ελw␈↓ αj␈εα<␈α
1␈↓ β-␈εα0␈↓ ∧∧␈εα,␈α∞since␈α∞w␈α␈e␈α
w␈α␈ould␈α∞need␈α∞to␈α
tak␈α␈e␈↓ πk␈ελn␈↓ λ
␈εα=␈↓ λ>␈ελm␈↓ λg␈εα+␈α	1.␈α⊃In␈α
this␈α∞case␈α
w␈α␈e
␈β
∂␈↓ λ
␈εm␈↓ 
"␈εm
␈β
∀␈↓ ↓H␈εαcan␈αobtain␈αthe␈αleading␈αdigit␈αof␈↓ ¬,␈ελu␈↓ ¬M␈εαby␈αcomputing␈ε⊗␈αb␈↓ π?␈ελu␈↓ πT␈εα/1␈↓ πx␈εα0␈↓ λ$␈ε⊗c␈εα;␈αthen␈↓ 	→␈ελu␈↓ 	4␈εαmod␈↓ 	}␈εα1␈↓ 
⊂␈εα0␈↓ 
G␈εαcan␈αbe
␈β
?␈↓ ↓H␈εαcon␈α␈v␈α␈erted␈αas␈αabo␈α␈v␈α␈e␈αwith␈↓ ∧P␈ελn␈↓ ∧o␈εα=␈↓ ¬≥␈ελm␈↓ ¬=␈εα.
␈β
j␈↓ α␈εαThe␈α∞fact␈α∞that␈α∞the␈α∞answ␈α␈er␈α
digits␈α∞are␈α∞obtained␈α∞from␈α∞left␈α∞to␈α∞righ␈α␈t␈α∞may␈α∞be␈α
an
␈β∞∃␈↓ ↓H␈εαadvan␈α␈tage␈α∞in␈α∞some␈α∞applications␈α∞(e.g.,␈α∞when␈α∞typing␈α∞out␈α∞the␈α∞answ␈α␈er␈α∞one␈α∞digit␈α∞at
␈β∞A␈↓ ↓H␈εαa␈α∂time).␈α↔Th␈α␈us␈α⊂w␈α␈e␈α⊂see␈α∂that␈α⊂a␈α⊂fractional␈α∂method␈α⊂can␈α⊂be␈α∂used␈α⊂for␈α⊂con␈α␈v␈α␈ersion␈α∂of
␈β∞l␈↓ ↓H␈εαin␈α␈tegers,␈α∩although␈α⊂the␈α⊃use␈α⊃of␈α⊂inexact␈α⊃division␈α⊃mak␈α␈es␈α⊃a␈α⊂little␈α⊃bit␈α⊃of␈α⊂n␈α␈umerical
␈β∂↔␈↓ ↓H␈εαanalysis␈αnecessary.
␈β∂B␈↓ α␈εαA␈α	modi|cation␈α	of␈αλMethod␈α	(1a)␈α	can␈α	be␈αλused␈α	to␈α	av␈α␈oid␈α	division␈αλby␈α	10,␈α
by␈αλreplac-
␈β∂m␈↓ ↓H␈εαing␈α∞it␈α∂with␈α∂t␈α␈w␈α␈o␈α∂m␈α␈ultiplications.␈α∀It␈α∂is␈α∞w␈α␈orth␈α∂men␈α␈tioning␈α∂this␈α∂modi|cation␈α∞here,
␈β⊂→␈↓ ↓H␈εαbecause␈αradix␈αcon␈α␈v␈α␈ersion␈αis␈αoften␈αdone␈αby␈αsmall␈α\satellite"␈αcomputers␈αthat␈αhav␈α␈e
␈β⊂A␈↓ λf␈ε¬1␈↓ 
~␈ε¬1
␈β⊂D␈↓ ↓H␈εαno␈αdivision␈αcapability.␈αIf␈αw␈α␈e␈αlet␈↓ ¬>␈ελx␈↓ ¬\␈εαbe␈αan␈αappro␈α␈ximation␈αto␈↓ λ␈␈εα,␈αso␈αthat␈↓ 
>␈εα<␈↓ 
l␈ελx␈↓ λ␈εα<
␈β⊂T␈↓ λ←␈∧⊂Tλ←α≥␈↓ 
∪␈∧⊂T
∪α≥
␈β⊂W␈↓ λ←␈ε¬10␈↓ 
∪␈ε¬10
␈β⊂l␈↓ ↓S␈ε¬1
␈β⊂o␈↓ ↓t␈εα+␈αλ1/␈↓ αD␈ελw␈↓ α↑␈εα,␈αit␈αis␈αeasy␈αto␈αpro␈α␈v␈α␈e␈α(see␈αex␈α␈ercise␈α7)␈αthat␈ε⊗␈αb␈↓ πh␈ελu␈↓ π}␈ελx␈↓ λ⊃␈ε⊗c␈εα␈α
=␈ε⊗␈α
b␈↓ λe␈ελu␈↓ λz␈εα/10␈ε⊗c␈εα␈αor␈ε⊗␈αb␈↓ 
∧␈ελu␈↓ 
→␈εα/10␈ε⊗c␈εα␈αλ+␈απ1,
␈β⊂␈␈↓ ↓L␈∧⊂␈↓Lα≥
␈β⊃α␈↓ ↓L␈ε¬10
␈β⊃~␈↓ ↓H␈εαso␈αlong␈αas␈α0␈ε⊗␈α
∀␈↓ β8␈ελu␈↓ βX␈εα<␈↓ ∧ε␈ελw␈↓ ∧!␈εα.␈αTherefore,␈αif␈α
w␈α␈e␈αcompute␈↓ πO␈ελu␈↓ πl␈ε⊗␈␈εα␈αλ10␈ε⊗b␈↓ λJ␈ελu␈↓ λ`␈ελx␈↓ λs␈ε⊗c␈εα,␈αw␈α␈e␈αwill␈αbe␈αable␈αto
␈β∪(

␈β↓Y␈↓ ↓H␈εα302␈↓ α=␈ε∞A␈α␈RITH␈α␈METIC␈εα␈↓ 
}4.4
␈βα&␈↓ ↓H␈εαdetermine␈αthe␈αvalue␈αof␈ε⊗␈αb␈↓ ∧F␈ελu␈↓ ∧[␈εα/10␈ε⊗c␈εα:
␈βα|␈↓ ∧{␈ε↓~
␈ββ↓␈↓ ¬⊃␈ε⊗b␈↓ ¬∨␈ελu␈↓ ¬4␈ελx␈↓ ¬G␈ε⊗c␈εα,␈↓ εm␈εαif␈↓ π∂␈ελu␈↓ π-␈ε⊗␈␈εα␈αλ10␈ε⊗b␈↓ λ␈ελu␈↓ λ ␈ελx␈↓ λ3␈ε⊗c␈α
∃␈εα␈α
0;
␈ββ⊗␈↓ β[␈ε⊗b␈↓ βi␈ελu␈↓ β␈␈εα/10␈ε⊗c␈εα␈α
=␈↓ α␈εα(5)
␈ββ,␈↓ ¬⊃␈ε⊗b␈↓ ¬∨␈ελu␈↓ ¬4␈ελx␈↓ ¬G␈ε⊗c␈αλ␈␈εα␈αλ1,␈↓ εm␈εαif␈↓ π∂␈ελu␈↓ π-␈ε⊗␈␈εα␈αλ10␈ε⊗b␈↓ λ␈ελu␈↓ λ ␈ελx␈↓ λ3␈ε⊗c␈εα␈α
<␈α
0.
␈β∧¬␈↓ ↓H␈εαThis␈αprocedure␈αsim␈α␈ultaneously␈αdetermines␈↓ εg␈ελu␈↓ πα␈εαmod␈↓ πL␈εα10.␈αA␈ε∃␈αMIX␈εα␈α
program␈αfor␈αcon␈α␈v␈α␈er-
␈β∧0␈↓ ↓H␈εαsion␈α
using␈α∞this␈α∞idea␈α
appears␈α∞in␈α∞ex␈α␈ercise␈α∞8;␈α∞it␈α∞requires␈α∞about␈α
33␈α∞cy␈α␈cles␈α∞per␈α
digit.
␈β∧\␈↓ α␈εαThe␈αλprocedure␈αλrepresen␈α␈ted␈αλby␈α	(5)␈αλcan␈αλbe␈αλused␈αλe{ectiv␈α␈ely␈αλev␈α␈en␈αλif␈αλthe␈αλcomputer
␈β¬λ␈↓ ↓H␈εαhas␈αno␈α
built-in␈α
m␈α␈ultiplication␈αinstruction,␈α
since␈α
m␈α␈ultiplication␈αby␈α
10␈α
consists␈αof
␈β¬.␈↓ ελ␈ε¬3
␈β¬3␈↓ ↓H␈εαt␈α␈w␈α␈o␈α
shifts␈α∞and␈α
one␈α∞addition␈α
(10␈α
=␈↓ ¬v␈εα2␈↓ ε∨␈εα+␈α	2).␈α⊃Ev␈α␈en␈α
the␈α∞task␈α
of␈α∞m␈α␈ultiplication␈α
by
␈β¬[␈↓ ↓S␈ε¬1
␈β¬↑␈↓ ↓y␈εαcan␈α
be␈α
done␈α
by␈α
judiciously␈α
com␈α␈bining␈α
a␈α
few␈α
shifting␈α
and␈α
adding␈αoperations,
␈β¬n␈↓ ↓L␈∧¬n↓Lα≥
␈β¬q␈↓ ↓L␈ε¬10
␈βε	␈↓ ↓H␈εαas␈αexplained␈αin␈αex␈α␈ercise␈α9.
␈βε6␈↓ α␈εαAnother␈α
way␈αto␈α
con␈α␈v␈α␈ert␈α
from␈αbinary␈α
to␈αdecimal␈α
is␈α
to␈αuse␈α
Method␈α
(1b),␈αbut
␈βεa␈↓ ↓H␈εαto␈αdo␈αthis␈α
w␈α␈e␈αneed␈α
to␈αsim␈α␈ulate␈α
doubling␈αin␈αa␈ε∂␈α
decimal␈εα␈αn␈α␈um␈α␈ber␈α
system.␈α
This␈αidea
␈βπ␈↓ ↓H␈εαis␈α
generally␈αmost␈αsuitable␈αfor␈αincorporation␈αin␈α␈to␈α
computer␈αhardware;␈αho␈α␈w␈α␈ev␈α␈er,␈αit
␈βπ7␈↓ ↓H␈εαis␈α∞possible␈α∞to␈α∞program␈α∞the␈α∞doubling␈α∞process␈α∞for␈α∞decimal␈α∞n␈α␈um␈α␈bers,␈α∞using␈α∞binary
␈βπc␈↓ ↓H␈εαaddition,␈α
binary␈α
shifting,␈α
and␈α
binary␈α
extraction␈α
(\logical␈↓ λB␈ε∃AND␈↓ 	␈εα"␈α
on␈α
each␈α
bit␈α
in␈α
the
␈βλ∞␈↓ ↓H␈εαregister),␈αas␈αsho␈α␈wn␈αin␈αTable␈α1.
␈βλW␈↓ ¬{␈ε≥Ta␈α␈b␈α↓le␈α
1
␈β	∂␈↓ β≤␈εβDOUBLING␈αA␈αBINAR␈α⎇Y-CODED␈αDECIMAL␈αNUMBER
␈β	O␈↓ α$␈ε⊂Op␈α␈eration␈↓ ¬≤␈ε⊂Gen␈α␈eral␈αform␈↓ λ@␈ε⊂Exam␈α␈ple
␈β	}␈↓ ↓␈␈εβ1.␈↓ α$␈εβGiv␈α␈e␈α␈n␈↓ ∧ ␈ε	u␈↓ ∧@␈ε	u␈↓ ∧←␈ε	u␈↓ ∧␈␈ε	u␈↓ ¬*␈ε	u␈↓ ¬J␈ε	u␈↓ ¬i␈ε	u␈↓ ε	␈ε	u␈↓ ε9␈ε	u␈↓ ε]␈ε	u␈↓ π	␈ε	u␈↓ π6␈ε	u␈↓ λ∨␈εβ00␈α␈11␈α0␈α␈110␈α
100␈α␈1␈↓ 
ε␈εβ=␈α
3␈α	6␈α	9
␈β
	␈↓ ∧3␈εε1␈↓ ∧S␈εε2␈↓ ∧s␈εε3␈↓ ¬∩␈εε4␈↓ ¬=␈εε5␈↓ ¬]␈εε6␈↓ ¬⎇␈εε7␈↓ ε≤␈εε8␈↓ εL␈εε9␈↓ εp␈εε10␈↓ π≤␈εε11␈↓ πI␈εε1␈α␈2
␈β
&␈↓ α$␈εβn␈α}um␈α␈b␈α␈er
␈β
M␈↓ ↓␈␈εβ2.␈↓ α$␈εβAd␈α␈d␈α3␈αto␈↓ ∧"␈ε	v␈↓ ∧B␈ε	v␈↓ ∧b␈ε	v␈↓ ¬↓␈ε	v␈↓ ¬,␈ε	v␈↓ ¬L␈ε	v␈↓ ¬l␈ε	v␈↓ ε␈ε	v␈↓ ε;␈ε	v␈↓ ε←␈ε	v␈↓ π␈ε	v␈↓ π8␈ε	v␈↓ λ∨␈εβ01␈α␈10␈α1␈α␈001␈α
110␈α␈0
␈β
X␈↓ ∧1␈εε1␈↓ ∧Q␈εε2␈↓ ∧p␈εε3␈↓ ¬⊂␈εε4␈↓ ¬;␈εε5␈↓ ¬[␈εε6␈↓ ¬z␈εε7␈↓ ε~␈εε8␈↓ εJ␈εε9␈↓ εn␈εε1␈α␈0␈↓ π~␈εε11␈↓ πG␈εε1␈α␈2
␈β
u␈↓ α$␈εβea␈α␈ch␈αd␈α␈igit
␈β≤␈↓ ↓␈␈εβ3.␈↓ α$␈εβS␈α␈hift␈αl␈α↓e␈α␈ft␈↓ βy␈ε	v␈↓ ∧"␈ε	v␈↓ ∧B␈ε	v␈↓ ∧b␈ε	v␈↓ ¬↓␈ε	v␈↓ ¬,␈ε	v␈↓ ¬L␈ε	v␈↓ ¬l␈ε	v␈↓ ε␈ε	v␈↓ ε5␈ε	v␈↓ ε←␈ε	v␈↓ π␈ε	v␈↓ πC␈εβ0␈↓ λβ␈εβ0␈α11␈α␈01␈α0␈α␈011␈α
100␈α␈0
␈β'␈↓ ∧λ␈εε1␈↓ ∧1␈εε2␈↓ ∧Q␈εε3␈↓ ∧p␈εε4␈↓ ¬⊂␈εε5␈↓ ¬;␈εε6␈↓ ¬[␈εε7␈↓ ¬z␈εε8␈↓ ε~␈εε9␈↓ εC␈εε10␈↓ εn␈εε1␈α␈1␈↓ π~␈εε12
␈βD␈↓ α$␈εβon␈α␈e
␈βl␈↓ ↓␈␈εβ4.␈↓ α$␈εβExtr␈α␈act␈αlo␈α␈w␈↓ βy␈ε	v␈↓ ∧(␈εβ0␈↓ ∧G␈εβ0␈↓ ∧g␈εβ0␈↓ ¬↓␈ε	v␈↓ ¬2␈εβ0␈↓ ¬Q␈εβ0␈↓ ¬q␈εβ0␈↓ ε␈ε	v␈↓ ε@␈εβ0␈↓ εk␈εβ0␈↓ π↔␈εβ0␈↓ πC␈εβ0␈↓ λβ␈εβ0␈α00␈α␈01␈α0␈α␈001␈α
000␈α␈0
␈βv␈↓ ∧λ␈εε1␈↓ ¬⊂␈εε5␈↓ ε~␈εε9
␈β∪␈↓ α$␈εβb␈α␈i␈α↓t
␈β;␈↓ ↓␈␈εβ5.␈↓ α$␈εβS␈α␈hift␈αrigh␈α␈t␈↓ ∧(␈εβ0␈↓ ∧B␈ε	v␈↓ ∧g␈εβ0␈↓ ¬π␈εβ0␈↓ ¬2␈εβ0␈↓ ¬L␈ε	v␈↓ ¬q␈εβ0␈↓ ε⊃␈εβ0␈↓ ε@␈εβ0␈↓ εe␈ε	v␈↓ π↔␈εβ0␈↓ πC␈εβ0␈↓ λ∨␈εβ00␈α␈00␈α0␈α␈100␈α
010␈α␈0
␈βE␈↓ ∧Q␈εε1␈↓ ¬[␈εε5␈↓ εt␈εε9
␈βb␈↓ α$␈εβt␈α␈w␈α␈o
␈β
␈↓ ↓␈␈εβ6.␈↓ α$␈εβS␈α␈hift␈αrigh␈α␈t␈↓ ∧(␈εβ0␈↓ ∧B␈ε	v␈↓ ∧b␈ε	v␈↓ ¬π␈εβ0␈↓ ¬2␈εβ0␈↓ ¬L␈ε	v␈↓ ¬l␈ε	v␈↓ ε⊃␈εβ0␈↓ ε@␈εβ0␈↓ εe␈ε	v␈↓ π∩␈ε	v␈↓ πC␈εβ0␈↓ λ∨␈εβ00␈α␈00␈α0␈α␈110␈α
011␈α␈0
␈β
∃␈↓ ∧Q␈εε1␈↓ ∧p␈εε1␈↓ ¬[␈εε5␈↓ ¬z␈εε5␈↓ εt␈εε9␈↓ π ␈εε9
␈β
2␈↓ α$␈εβon␈α␈e␈αan␈α␈d␈αa␈α␈dd
␈β
Y␈↓ ↓␈␈εβ7.␈↓ α$␈εβAd␈α␈d␈αresu␈α␈lt␈↓ β}␈ε↔β␈↓ ∧(␈ε↔β␈↓ ∧G␈ε↔β␈↓ ∧g␈ε↔β␈↓ ¬π␈ε↔β␈↓ ¬2␈ε↔β␈↓ ¬Q␈ε↔β␈↓ ¬q␈ε↔β␈↓ ε⊃␈ε↔β␈↓ ε@␈ε↔β␈↓ εk␈ε↔β␈↓ π↔␈ε↔β␈↓ πC␈εβ0␈↓ λβ␈εβ0␈α11␈α␈01␈α1␈α␈001␈α
111␈α␈0
␈β∞↓␈↓ α$␈εβof␈αste␈α␈p␈α3
␈β∞(␈↓ ↓␈␈εβ8.␈↓ α$␈εβS␈α␈ub␈α␈tract␈α6␈↓ βy␈ε	y␈↓ ∧"␈ε	y␈↓ ∧A␈ε	y␈↓ ∧a␈ε	y␈↓ ¬↓␈ε	y␈↓ ¬,␈ε	y␈↓ ¬K␈ε	y␈↓ ¬k␈ε	y␈↓ ε␈ε	y␈↓ ε4␈ε	y␈↓ ε←␈ε	y␈↓ π␈ε	y␈↓ πC␈εβ0␈↓ λβ␈εβ0␈α01␈α␈11␈α0␈α␈011␈α
100␈α␈0␈↓ 
ε␈εβ=␈α
7␈α	3␈α	8
␈β∞3␈↓ ∧λ␈εε1␈↓ ∧1␈εε2␈↓ ∧Q␈εε3␈↓ ∧q␈εε4␈↓ ¬⊃␈εε5␈↓ ¬;␈εε6␈↓ ¬[␈εε7␈↓ ¬{␈εε8␈↓ ε≠␈εε9␈↓ εD␈εε1␈α␈0␈↓ εn␈εε11␈↓ π≠␈εε1␈α␈2
␈β∞P␈↓ α$␈εβfrom␈α
each
␈β∞x␈↓ λ␈ε↓␈
␈β∂↔␈↓ α␈εαThis␈α
method␈α	changes␈α	each␈α
individual␈α	digit␈↓ π'␈ελd␈↓ πE␈εαin␈α␈to␈↓ λ→␈εα(␈↓ λ%␈ελd␈↓ λ>␈εα+␈α∧3)␈ε⊗␈α¬α␈εα␈α¬2␈α∧+␈α¬0)␈ε⊗␈α¬␈␈εα␈α∧6␈α
=␈α
2␈↓ _␈ελd
␈β∂#␈↓ ¬≥␈ε↓␈␈↓ π8␈ε↓↓
␈β∂>␈↓ 
<␈ε¬4
␈β∂C␈↓ ↓H␈εαwhen␈α∂0␈ε⊗␈α⊃∀␈↓ β␈ελd␈↓ β%␈ε⊗∀␈εα␈α⊂4,␈α⊃and␈α⊂in␈α␈to␈↓ ¬+␈εα(␈↓ ¬7␈ελd␈↓ ¬U␈εα+␈α3)␈ε⊗␈α
α␈εα␈α2␈α
+␈α6␈↓ πQ␈ε⊗␈␈εα␈α
6␈α⊂=␈α⊃(2␈↓ λt␈ελd␈↓ 	∪␈ε⊗␈␈εα␈α
10)␈α+␈↓ 
*␈εα2␈↓ 
Z␈εαwhen
␈β∂n␈↓ ↓H␈εα5␈ε⊗␈α
∀␈↓ α∩␈ελd␈↓ α0␈ε⊗∀␈↓ α↑␈ελq␈↓ αn␈εα;␈αand␈αthat␈αis␈αjust␈αwhat␈αis␈αneeded␈αto␈αdouble␈αdecimal␈αn␈α␈um␈α␈bers␈αencoded
␈β⊂→␈↓ ↓H␈εαwith␈α4␈αbits␈αper␈αdigit.
␈β⊂F␈↓ α␈εαAnother␈α
related␈αidea␈α
is␈α
to␈αk␈α␈eep␈α
a␈αtable␈α
of␈α
the␈αpo␈α␈w␈α␈ers␈α
of␈α
t␈α␈w␈α␈o␈αin␈α
decimal␈α
form,
␈β⊂q␈↓ ↓H␈εαand␈α
to␈α
add␈α
the␈α∞appropriate␈α
po␈α␈w␈α␈ers␈α
together␈α
by␈α
sim␈α␈ulating␈α∞decimal␈α
addition.␈α∂A
␈β⊃≤␈↓ ↓H␈εαsurv␈α␈ey␈αof␈αsuch␈αbit-manipulation␈αtechniques␈αappears␈αin␈αSection␈α7.1.
␈β∪(

␈β↓Y␈↓ ↓H␈εα4.4␈ε∞␈↓ λ~R␈α↓A␈α␈DIX␈α	CONV␈α␈ERSION␈↓ 
v␈εα303
␈βα&␈↓ α␈εαFinally,␈αev␈α␈en␈αMethod␈α(2b)␈αcan␈αbe␈αused␈αfor␈αthe␈αcon␈α␈v␈α␈ersion␈αof␈αbinary␈αin␈α␈tegers
␈βαQ␈↓ ↓H␈εαto␈α	decimal␈α	in␈α␈tegers.␈αWe␈α	can␈α
|nd␈↓ ¬B␈ελq␈↓ ¬[␈εαas␈α	in␈α	(2),␈α
and␈α	then␈α
w␈α␈e␈α	can␈α	sim␈α␈ulate␈α	the␈α	decimal
␈βα⎇␈↓ ↓H␈εαdivision␈α∞of␈↓ α⎇␈ελq␈↓ β↔␈εα+␈α
1␈α∂by␈↓ ∧≥␈ελw␈↓ ∧7␈εα,␈α⊂using␈α∂a␈α∂\halving"␈α∞process␈α∂(ex␈α␈ercise␈α∂10)␈α∂that␈α∂is␈α∞similar
␈ββ(␈↓ ↓H␈εαto␈α∂the␈α∂doubling␈α∂process␈α∂just␈α∂described,␈α⊂retaining␈α∂only␈α∂the␈α∂|rst␈↓ 	A␈ελn␈↓ 	f␈εαdigits␈α∂to␈α∂the
␈ββS␈↓ ↓H␈εαrigh␈α␈t␈α
of␈α∞the␈α∞radix␈α∞poin␈α␈t␈α∞in␈α∞the␈α
answ␈α␈er.␈α∩In␈α∞this␈α∞situation,␈α∞Method␈α∞(2b)␈α∞does␈α
not
␈ββ}␈↓ ↓H␈εαseem␈α
to␈α
o{er␈αadvan␈α␈tages␈α
o␈α␈v␈α␈er␈αthe␈α
other␈α
three␈αmethods␈α
already␈α
discussed,␈αbut␈α
w␈α␈e
␈β∧)␈↓ ↓H␈εαhav␈α␈e␈αcon|rmed␈α
the␈αremark␈α
made␈αearlier␈α
that␈αat␈α
least␈αfour␈αdistinct␈α
methods␈αare
␈β∧U␈↓ ↓H␈εαavailable␈αfor␈αcon␈α␈v␈α␈erting␈αin␈α␈tegers␈αfrom␈αone␈αradix␈αto␈αanother.
␈β¬⊗␈↓ α␈εαNo␈α␈w␈α
let␈α
us␈α
consider␈α
decimal-to-binary␈α
con␈α␈v␈α␈ersion␈α
(so␈α
that␈↓ 	,␈ελb␈↓ 	F␈εα=␈α10,␈↓ 
1␈ελB␈↓ 
U␈εα=␈α2).
␈β¬B␈↓ ↓H␈εαMethod␈α(1a)␈α
sim␈α␈ulates␈α
a␈αdecimal␈α
division␈α
by␈α2;␈α
this␈α
is␈αfeasible␈α
(see␈α
ex␈α␈ercise␈α10),
␈β¬m␈↓ ↓H␈εαbut␈αit␈αis␈αprimarily␈αsuitable␈αfor␈αincorporation␈αin␈αhardware␈αinstead␈αof␈αprograms.
␈βε≠␈↓ α␈εαMethod␈α
(1b)␈αis␈α
the␈αmost␈αpractical␈α
method␈αfor␈α
decimal-to-binary␈αcon␈α␈v␈α␈ersion
␈βεF␈↓ ↓H␈εαin␈αthe␈αgreat␈αmajority␈αof␈αcases.␈αHere␈αit␈αis␈αin␈ε∃␈αMIX␈εα␈α
code,␈αassuming␈αthat␈αthere␈αare␈αat
␈βεq␈↓ ↓H␈εαleast␈αt␈α␈w␈α␈o␈αdigits␈αin␈αthe␈αn␈α␈um␈α␈ber␈α(␈↓ ¬8␈ελu␈↓ ¬l␈εα.␈αε.␈αε.␈↓ ε≤␈ελu␈↓ ε?␈ελu␈↓ εb␈εα)␈↓ π↔␈εαbeing␈αcon␈α␈v␈α␈erted:
␈βε␈␈↓ ¬L␈εm␈↓ ε1␈ε¬1␈↓ εT␈ε¬0␈↓ εn␈ε¬10
␈βπH␈↓ βi␈ε∃ENT1␈↓ ∧f␈ε∃M␈α␈-1
␈βπK␈↓ εS␈εβSet␈↓ π
␈ε	j␈↓ π%␈ε↔ ␈↓ πO␈ε	m␈↓ πt␈ε↔␈␈εβ␈αλ1␈α␈.
␈βπp␈↓ βi␈ε∃LDA␈↓ ∧f␈ε∃I␈α␈NPU␈α␈T+M
␈βπs␈↓ εS␈εβSet␈↓ π
␈ε	U␈↓ π1␈ε↔ ␈↓ π\␈ε	u␈↓ λε␈εβ.
␈βπ}␈↓ πo␈εm
␈βλ_␈↓ β↔␈ε∃1␈α␈H␈↓ βi␈ε∃MUL␈↓ ∧f␈ε∃=␈α␈10=
␈βλ?␈↓ βi␈ε∃SLAX␈↓ ∧f␈ε∃5
␈βλ@␈↓ α␈εα(6)
␈βλg␈↓ βi␈ε∃ADD␈↓ ∧f␈ε∃I␈α␈NPU␈α␈T,1
␈βλj␈↓ εS␈ε	U␈↓ εx␈ε↔ ␈εβ␈α	10␈↓ πD␈ε	U␈↓ πf␈εβ+␈↓ λ∂␈ε	u␈↓ λ.␈εβ.
␈βλt␈↓ λ"␈εj
␈β	∞␈↓ βi␈ε∃DEC1␈↓ ∧f␈ε∃1
␈β	6␈↓ βi␈ε∃J1NN␈↓ ∧f␈ε∃1␈α␈B
␈β	9␈↓ εS␈εβRepe␈α␈at␈αfor␈↓ πy␈ε	m␈↓ λ∨␈εβ>␈↓ λJ␈ε	j␈↓ λb␈ε↔∃␈εβ␈α
0␈α␈.
␈β	;␈↓ 	K␈∧	;	K≠∂
␈β

␈↓ ↓H␈εαNote␈α	again␈α
that␈α
adding␈α	and␈α
shifting␈α
may␈α	be␈α
substituted␈α	for␈α
m␈α␈ultiplication␈α
by␈α	10.
␈β
;␈↓ α␈εαA␈α
trickier␈α	but␈α
perhaps␈α
faster␈α
method,␈α
which␈α
uses␈α	about␈↓ λn␈εαlg␈↓ 	⊂␈ελm␈↓ 	9␈εαm␈α␈ultiplications,
␈β
f␈↓ ↓H␈εαextractions,␈αλand␈αλadditions␈απinstead␈αλof␈↓ ¬␈␈ελm␈↓ ε&␈εαm␈α␈ultiplications␈αλand␈απadditions,␈α	is␈απdescribed
␈β∩␈↓ ↓H␈εαin␈αex␈α␈ercise␈α19.
␈β@␈↓ α␈εαFor␈α∂the␈α∂con␈α␈v␈α␈ersion␈α∂of␈α∂decimal␈α∂fractions␈α∂(0.␈↓ π:␈ελu␈↓ πz␈ελu␈↓ λ@␈εα.␈αε.␈αε.␈↓ λp␈ελu␈↓ 	;␈εα)␈↓ 	d␈εα,␈α∂w␈α␈e␈α∂can␈α∂use
␈βM␈↓ πO␈ε→␈␈ε¬␈α␈1␈↓ λ∞␈ε→␈␈ε¬2␈↓ 	∧␈ε→␈␈↓ 	!␈εm␈↓ 	G␈ε¬10
␈βk␈↓ ↓H␈εαMethod␈α	(2b),␈α	or,␈α
more␈α	commonly,␈α	w␈α␈e␈α	can␈α	con␈α␈v␈α␈ert␈α	the␈α	in␈α␈teger␈α	(␈↓ 	β␈ελu␈↓ 	C␈ελu␈↓ 
λ␈εα.␈αε.␈αε.␈↓ 
8␈ελu␈↓ ∧␈εα)
␈βx␈↓ 	↔␈ε→␈␈ε¬1␈↓ 	W␈ε→␈␈ε¬2␈↓ 
M␈ε→␈␈↓ 
j␈εm␈↓ ⊂␈ε¬10
␈β⊃␈↓ ε&␈εm
␈β⊗␈↓ ↓H␈εαby␈αMethod␈α(1b)␈αand␈αthen␈αdivide␈αby␈α1␈↓ ε∀␈εα0␈↓ ε@␈εα.
␈βk␈↓ ↓H␈ε∩C.␈αHand␈αcalculation.␈εα␈α→It␈α
is␈αoccasionally␈αnecessary␈αfor␈αcomputer␈αprogrammers␈αto
␈β
↔␈↓ ↓H␈εαcon␈α␈v␈α␈ert␈αλn␈α␈um␈α␈bers␈α	by␈α	hand,␈α	and␈α	since␈α	this␈α	is␈α	a␈αλsubject␈α	not␈α	y␈α␈et␈α	taugh␈α␈t␈α	in␈αλelemen␈α␈tary
␈β
B␈↓ ↓H␈εαschools,␈αit␈αmay␈αbe␈αw␈α␈orth␈αwhile␈αto␈αexamine␈αit␈αbrie⎇y␈αhere.␈αThere␈αare␈αv␈α␈ery␈αsimple
␈β
m␈↓ ↓H␈εαpencil-and-paper␈α∞methods␈α∞for␈α∂con␈α␈v␈α␈erting␈α∞bet␈α␈w␈α␈een␈α∞decimal␈α∂and␈α∞octal␈α∞notations,
␈β∞_␈↓ ↓H␈εαand␈αthese␈αmethods␈αare␈αeasily␈αlearned,␈αso␈αthey␈αough␈α␈t␈αto␈αbe␈αmore␈αwidely␈αkno␈α␈wn.
␈β∞n␈↓ ↓H␈ε∂Con␈α␈v␈α␈erting␈α
octal␈α
in␈α␈tegers␈α
to␈α
decimal.␈εα␈α≠The␈α
simplest␈α
con␈α␈v␈α␈ersion␈α
is␈α
from␈α
octal␈α
to
␈β∂→␈↓ ↓H␈εαdecimal;␈α
this␈α
technique␈α
was␈α
apparen␈α␈tly␈α
|rst␈α
published␈αby␈α
Walter␈α
Soden,␈ε∂␈α
Math.
␈β∂D␈↓ ↓H␈ε∂Comp.␈ε∩␈α	7␈εα␈α
(1953),␈α
273↑274.␈αTo␈α
do␈α
the␈α	con␈α␈v␈α␈ersion,␈α
write␈α
do␈α␈wn␈α
the␈α	giv␈α␈en␈α
octal␈α	n␈α␈um-
␈β∂o␈↓ ↓H␈εαber;␈α
then␈α
at␈α∞the␈↓ βQ␈ελk␈↓ βb␈εαth␈α∞step,␈α
double␈α
the␈↓ ε≥␈ελk␈↓ ε<␈εαleading␈α
digits␈α
using␈α
decimal␈α
arithmetic,
␈β⊂~␈↓ ↓H␈εαand␈α∞subtract␈α∞this␈α∞from␈α∞the␈↓ ¬␈ελk␈↓ ¬≠␈εα+␈α	1␈α∞leading␈α∞digits␈α∞using␈α∞decimal␈α∞arithmetic.␈α∩The
␈β⊂F␈↓ ↓H␈εαprocess␈αterminates␈α
in␈↓ ∧!␈ελn␈↓ ∧?␈ε⊗␈␈εα␈α	1␈αsteps␈α
if␈αthe␈α
giv␈α␈en␈α
n␈α␈um␈α␈ber␈αhas␈↓ λi␈ελn␈↓ 	␈εαdigits.␈α∞It␈αis␈α
a␈αgood
␈β⊂q␈↓ ↓H␈εαidea␈αto␈αinsert␈αa␈αradix␈αpoin␈α␈t␈αto␈αsho␈α␈w␈αwhich␈αdigits␈αare␈αbeing␈αdoubled,␈αas␈αsho␈α␈wn␈αin
␈β⊃≤␈↓ ↓H␈εαthe␈αfollo␈α␈wing␈αexample,␈αin␈αorder␈αto␈αprev␈α␈en␈α␈t␈αem␈α␈barrassing␈αmistak␈α␈es.
␈β∪(

␈β↓Y␈↓ ↓H␈εα304␈↓ α=␈ε∞A␈α␈RITH␈α␈METIC␈εα␈↓ 
}4.4
␈βα&␈↓ ↓H␈ε∩Example␈α1.␈εα␈α→Con␈α␈v␈α␈ert␈α(5325121␈↓ ¬)␈εα)␈↓ ¬O␈εαto␈αdecimal.
␈βα4␈↓ ¬5␈ε¬8
␈βββ␈↓ ∧0␈εα5␈↓ ∧F␈εα.␈↓ ∧T␈εα3␈α∩2␈α∩5␈α∩1␈α∩2␈α∩1
␈ββ/␈↓ ∧␈ε⊗␈␈↓ ∧0␈εα1␈α∩0
␈ββU␈↓ ∧0␈∧βU∧0α6
␈ββc␈↓ ∧0␈εα4␈α∩3␈↓ ∧j␈εα.␈↓ ∧x␈εα2␈α∩5␈α∩1␈α∩2␈α∩1
␈β∧∞␈↓ ∧␈ε⊗␈␈↓ ∧T␈εα8␈α∩6
␈β∧4␈↓ ∧0␈∧∧4∧0αZ
␈β∧B␈↓ ∧0␈εα3␈α∩4␈α∩6␈↓ ¬∞␈εα.␈↓ ¬≤␈εα5␈α∩1␈α∩2␈α∩1
␈β∧m␈↓ ∧␈ε⊗␈␈↓ ∧T␈εα6␈α∩9␈α∩2
␈β¬∪␈↓ ∧0␈∧¬∪∧0α}
␈β¬!␈↓ ∧0␈εα2␈α∩7␈α∩7␈α∩3␈↓ ¬2␈εα.␈↓ ¬@␈εα1␈α∩2␈α∩1
␈β¬L␈↓ ∧␈ε⊗␈␈↓ ∧T␈εα5␈α∩5␈α∩4␈α∩6
␈β¬r␈↓ ∧0␈∧¬r∧0α↓"
␈βε␈↓ ∧0␈εα2␈α∩2␈α∩1␈α∩8␈α∩5␈↓ ¬V␈εα.␈↓ ¬d␈εα2␈α∩1
␈βε+␈↓ ∧␈ε⊗␈␈↓ ∧T␈εα4␈α∩4␈α∩3␈α∩7␈α∩0
␈βεQ␈↓ ∧0␈∧εQ∧0α↓F
␈βε←␈↓ ∧0␈εα1␈α∩7␈α∩7␈α∩4␈α∩8␈α∩2␈↓ ¬z␈εα.␈↓ ελ␈εα1
␈βπ
␈↓ ∧␈ε⊗␈␈↓ ∧T␈εα3␈α∩5␈α∩4␈α∩9␈α∩6␈α∩4
␈βπ0␈↓ ∧0␈∧π0∧0α↓j
␈βπ>␈↓ ∧0␈εα1␈α∩4␈α∩1␈α∩9␈α∩8␈α∩5␈α∩7␈↓ π_␈ε∂Answ␈α␈er:␈εα␈α(14198757␈↓ 	=␈εα)␈↓ 	e␈ε∂.
␈βπK␈↓ 	I␈ε¬10
␈βλ_␈↓ α␈εαA␈αreasonably␈αgood␈α
check␈αon␈αthe␈αcomputations␈αmay␈α
be␈αhad␈αby␈α\casting␈αout
␈βλD␈↓ ↓H␈εαnines":␈αThe␈αsum␈αof␈αthe␈αdigits␈αof␈αthe␈αdecimal␈αn␈α␈um␈α␈ber␈αm␈α␈ust␈αequal␈αthe␈αalternating
␈βλo␈↓ ↓H␈εαsum␈αand␈αdi{erence␈αof␈αthe␈αdigits␈αof␈αthe␈αoctal␈αn␈α␈um␈α␈ber,␈αwith␈αthe␈αrigh␈α␈tmost␈αdigit␈αof
␈β	~␈↓ ↓H␈εαthe␈αlatter␈αgiv␈α␈en␈αa␈αplus␈αsign,␈αex␈α␈cept␈αfor␈αa␈αm␈α␈ultiple␈αof␈αnine.␈αIn␈αthe␈αabo␈α␈v␈α␈e␈αexample,
␈β	E␈↓ ↓H␈εαw␈α␈e␈α
hav␈α␈e␈α
1␈αε+␈α¬4␈αε+␈α¬1␈αε+␈α¬9␈αε+␈αε8␈α¬+␈αε5␈α¬+␈αε7␈α
=␈α
35,␈α
and␈α1␈ε⊗␈α¬␈␈εα␈αε2␈α¬+␈αε1␈ε⊗␈α¬␈␈εα␈αε5␈αε+␈α¬2␈ε⊗␈αε␈␈εα␈α¬3␈αε+␈α¬5␈α
=␈ε⊗␈α
␈␈εα1;
␈β	p␈↓ ↓H␈εαthe␈αλdi{erence␈α	is␈α	36␈α	(a␈αλm␈α␈ultiple␈α	of␈α	9).␈αIf␈α	this␈αλtest␈α	fails,␈α
it␈αλcan␈α	be␈α	applied␈α	to␈α	the␈↓ 
]␈ελk␈↓ 
s␈εα+␈αβ1
␈β
≤␈↓ ↓H␈εαleading␈α∞digits␈α∞after␈α∞the␈↓ ∧B␈ελk␈↓ ∧T␈εαth␈α∞step,␈α∂and␈α∞the␈α∞error␈α∂can␈α∞be␈α∞located␈α∞using␈α∞a␈α∞\binary
␈β
G␈↓ ↓H␈εαsearch"␈α
procedure;␈α∂i.e.,␈α∞start␈α
by␈α∞checking␈α
the␈α∞middle␈α∞result,␈α∞then␈α
use␈α∞the␈α
same
␈β
r␈↓ ↓H␈εαprocedure␈α∞on␈α∞the␈α∞|rst␈α∞or␈α∞second␈α∞half␈α∞of␈α∞the␈α∞calculation,␈α∞depending␈α∞on␈α∞whether
␈β≥␈↓ ↓H␈εαthe␈αmiddle␈αresult␈αis␈αincorrect␈αor␈αcorrect.
␈βJ␈↓ α␈εαThe␈α∂\casting-out-nines"␈α∞process␈α∂is␈α∞only␈α∂about␈α∞89␈α∂percen␈α␈t␈α∞reliable,␈α∂because
␈βu␈↓ ↓H␈εαthere␈αis␈αone␈αchance␈αin␈αnine␈αthat␈αt␈α␈w␈α␈o␈ε∂␈αrandom␈εα␈αin␈α␈tegers␈αwill␈αdi{er␈αby␈αa␈αm␈α␈ultiple␈αof
␈β ␈↓ ↓H␈εαnine.␈α⊂An␈α∞ev␈α␈en␈α∞better␈α
check␈α∞is␈α
to␈α∞con␈α␈v␈α␈ert␈α
the␈α∞answ␈α␈er␈α∞back␈α
to␈α∞octal␈α
by␈α∞using␈α
an
␈βK␈↓ ↓H␈εαin␈α␈v␈α␈erse␈αmethod,␈αwhich␈αw␈α␈e␈αshall␈αno␈α␈w␈αconsider.
␈β
∪␈↓ ↓H␈ε∂Con␈α␈v␈α␈erting␈α
decimal␈α∞in␈α␈tegers␈α
to␈α∞octal.␈εα␈α≤A␈α∞similar␈α
procedure␈α∞can␈α∞be␈α
used␈α∞for␈α
the
␈β
?␈↓ ↓H␈εαopposite␈α	con␈α␈v␈α␈ersion:␈αWrite␈α
do␈α␈wn␈α	the␈α
giv␈α␈en␈α	decimal␈α
n␈α␈um␈α␈ber;␈α
then␈α
at␈α	the␈↓ 
%␈ελk␈↓ 
7␈εαth␈α	step,
␈β
j␈↓ ↓H␈εαdouble␈α∞the␈↓ α}␈ελk␈↓ β≡␈εαleading␈α∞digits␈α∞using␈ε∂␈α∞octal␈εα␈α∞arithmetic,␈α∂and␈ε∂␈α∞add␈εα␈α∞these␈α∂to␈α∞the␈↓ 
R␈ελk␈↓ 
m␈εα+␈α	1
␈β∞∃␈↓ ↓H␈εαleading␈α∞digits␈α∞using␈ε∂␈α∞octal␈εα␈α∞arithmetic.␈α∪The␈α∞process␈α∞terminates␈α∞in␈↓ 	N␈ελn␈↓ 	m␈ε⊗␈␈εα␈α	1␈α∞steps␈α∞if
␈β∞@␈↓ ↓H␈εαthe␈αgiv␈α␈en␈αn␈α␈um␈α␈ber␈αhas␈↓ ∧'␈ελn␈↓ ∧H␈εαdigits.␈α(See␈αexample␈α2␈αon␈αthe␈αfollo␈α␈wing␈αpage.)
␈β∞m␈↓ α␈εαThe␈α⊂t␈α␈w␈α␈o␈α∂procedures␈α⊂just␈α⊂giv␈α␈en␈α∂are␈α⊂essen␈α␈tially␈α⊂Method␈α∂(1b)␈α⊂of␈α⊂the␈α∂general
␈β∂_␈↓ ↓H␈εαradix-con␈α␈v␈α␈ersion␈α∂procedures.␈α↔Doubling␈α∂and␈α⊂subtracting␈α∂in␈α∂decimal␈α⊂notation␈α∂is
␈β∂C␈↓ ↓H␈εαlik␈α␈e␈α∞m␈α␈ultiplying␈α∞by␈α∂10␈ε⊗␈α	␈␈εα␈α
2␈α∞=␈α∞8;␈α∂doubling␈α∞and␈α∂adding␈α∞in␈α∞octal␈α∂notation␈α∞is␈α∞lik␈α␈e
␈β∂n␈↓ ↓H␈εαm␈α␈ultiplying␈αby␈α8␈αλ+␈αλ2␈α
=␈α
10.␈αThere␈αis␈αa␈αsimilar␈αmethod␈αfor␈αhexadecimal/decimal
␈β⊂→␈↓ ↓H␈εαcon␈α␈v␈α␈ersions,␈α
but␈α
it␈α
is␈α
a␈α∞little␈α
more␈α
di}cult␈α
since␈α
it␈α
in␈α␈v␈α␈olv␈α␈es␈α
m␈α␈ultiplication␈α
by␈α
6
␈β⊂E␈↓ ↓H␈εαinstead␈αof␈αby␈α2.
␈β⊂q␈↓ α␈εαTo␈α
k␈α␈eep␈α	these␈α
t␈α␈w␈α␈o␈α
methods␈α	straigh␈α␈t␈α
in␈α
our␈α	minds,␈α
it␈α
is␈α
not␈α	hard␈α
to␈α	remem␈α␈ber
␈β⊃≤␈↓ ↓H␈εαthat␈αεw␈α␈e␈απm␈α␈ust␈απsubtract␈απto␈απgo␈απfrom␈αεoctal␈απto␈απdecimal,␈αλsince␈απthe␈απdecimal␈αεrepresen␈α␈tation
␈β∪(

␈β↓Y␈↓ ↓H␈εα4.4␈ε∞␈↓ λ~R␈α↓A␈α␈DIX␈α	CONV␈α␈ERSION␈↓ 
v␈εα305
␈βα∨␈↓ ↓H␈ε∩Example␈α2.␈εα␈α→Con␈α␈v␈α␈ert␈α(1419857␈↓ ¬)␈εα)␈↓ ¬↑␈εαto␈αoctal.
␈βα,␈↓ ¬5␈ε¬10
␈βαg␈↓ ∧0␈εα1␈↓ ∧F␈εα.␈↓ ∧T␈εα4␈α∩1␈α∩9␈α∩8␈α∩5␈α∩7
␈ββ∩␈↓ ∧␈εα+␈↓ ∧T␈εα2
␈ββ9␈↓ ∧0␈∧β9∧0α6
␈ββF␈↓ ∧0␈εα1␈α∩6␈↓ ∧j␈εα.␈↓ ∧x␈εα1␈α∩9␈α∩8␈α∩5␈α∩7
␈ββ`␈↓ π_␈εα(Note␈α∩that␈α∩the␈α∩nonoctal␈α∩digits␈α∩8
␈ββq␈↓ ∧␈εα+␈↓ ∧T␈εα3␈α∩4
␈β∧␈↓ π_␈εαand␈α⊃9␈α∩en␈α␈ter␈α∩in␈α␈to␈α∩this␈α∩octal␈α⊃com-
␈β∧_␈↓ ∧0␈∧∧_∧0αZ
␈β∧%␈↓ ∧0␈εα2␈α∩1␈α∩5␈↓ ¬∞␈εα.␈↓ ¬≤␈εα9␈α∩8␈α∩5␈α∩7
␈β∧6␈↓ π_␈εαputation.)␈α/The␈α↔answ␈α␈er␈α_can␈α↔be
␈β∧P␈↓ ∧␈εα+␈↓ ∧T␈εα4␈α∩3␈α∩2
␈β∧a␈↓ π_␈εαcheck␈α␈ed␈α∞as␈α∂discussed␈α∂abo␈α␈v␈α␈e.␈α∪This
␈β∧w␈↓ ∧0␈∧∧w∧0α}
␈β¬∧␈↓ ∧0␈εα2␈α∩6␈α∩1␈α∩3␈↓ ¬2␈εα.␈↓ ¬@␈εα8␈α∩5␈α∩7
␈β¬
␈↓ π_␈εαmethod␈αwas␈αpublished␈αby␈αCharles
␈β¬/␈↓ ∧␈εα+␈↓ ∧T␈εα5␈α∩4␈α∩2␈α∩6
␈β¬8␈↓ π_␈εαP.␈α↔Rozier,␈ε∂␈α≠IEEE␈α_Trans.␈ε∩␈α↔CE↑11
␈β¬V␈↓ ∧0␈∧¬V∧0α↓"
␈β¬c␈↓ ∧0␈εα3␈α∩3␈α∩5␈α∩6␈α∩6␈↓ ¬V␈εα.␈↓ ¬d␈εα5␈α∩7␈↓ π_␈εα(1962),␈α708↑709.
␈βε∞␈↓ ∧␈εα+␈↓ ∧T␈εα6␈α∩7␈α∩3␈α∩5␈α∩4
␈βε5␈↓ ∧0␈∧ε5∧0α↓F
␈βεB␈↓ ∧0␈εα4␈α∩2␈α∩5␈α∩2␈α∩4␈α∩1␈↓ ¬z␈εα.␈↓ ελ␈εα7
␈βεm␈↓ ∧␈εα+␈↓ ∧0␈εα1␈α∩0␈α∩5␈α∩2␈α∩5␈α∩0␈α∩2
␈βπ∀␈↓ ∧0␈∧π∀∧0α↓j
␈βπ!␈↓ ∧0␈εα5␈α∩3␈α∩2␈α∩5␈α∩1␈α∩2␈α∩1␈↓ π_␈ε∂Answ␈α␈er:␈εα␈α(5325121␈↓ 	+␈εα)␈↓ 	E␈ε∂.
␈βπ.␈↓ 	7␈ε¬8
␈βλ¬␈↓ ↓H␈εαof␈αa␈αn␈α␈um␈α␈ber␈α
is␈αsmaller;␈α
similarly␈αw␈α␈e␈α
m␈α␈ust␈αadd␈αto␈α
go␈αfrom␈αdecimal␈α
to␈αoctal.␈α
The
␈βλ0␈↓ ↓H␈εαcomputations␈αare␈αperformed␈αusing␈αthe␈αradix␈αof␈α
the␈ε∂␈αansw␈α␈er␈εα,␈αnot␈αthe␈αradix␈αof␈αthe
␈βλ[␈↓ ↓H␈εαgiv␈α␈en␈αn␈α␈um␈α␈ber,␈αotherwise␈αw␈α␈e␈αcouldn't␈αget␈αthe␈αdesired␈αansw␈α␈er.
␈β	∀␈↓ ↓H␈ε∂Con␈α␈v␈α␈erting␈αfractions.␈εα␈α"No␈αequally␈αfast␈αmethod␈αof␈αcon␈α␈v␈α␈erting␈αfractions␈α
man␈α␈ually
␈β	?␈↓ ↓H␈εαis␈α⊂kno␈α␈wn;␈α∪the␈α⊃best␈α⊃way␈α⊂seems␈α⊃to␈α⊂be␈α⊃Method␈α⊃(2a),␈α∩with␈α⊂doubling␈α⊃and␈α⊂adding
␈β	k␈↓ ↓H␈εαor␈α∂subtracting␈α∂to␈α∂simplify␈α⊂the␈α∂m␈α␈ultiplications␈α∂by␈α∂10␈α⊂or␈α∂by␈α∂8.␈α⊗In␈α∂this␈α∂case,␈α⊂w␈α␈e
␈β
⊗␈↓ ↓H␈εαrev␈α␈erse␈α∂the␈α∞addition-subtraction␈α∂criterion,␈α⊂adding␈α∂when␈α∂w␈α␈e␈α∂con␈α␈v␈α␈ert␈α∂to␈α∞decimal
␈β
A␈↓ ↓H␈εαand␈α∂subtracting␈α∂when␈α∂w␈α␈e␈α∂con␈α␈v␈α␈ert␈α∂to␈α⊂octal;␈α⊂w␈α␈e␈α∂also␈α⊂use␈α∂the␈α∂radix␈α∂of␈α∂the␈α∂giv␈α␈en
␈β
l␈↓ ↓H␈εαinput␈αn␈α␈um␈α␈ber,␈ε∂␈αnot␈εα␈αthe␈αradix␈αof␈αthe␈αansw␈α␈er,␈αin␈αthis␈αcomputation␈α(see␈αExamples␈α3
␈β↔␈↓ ↓H␈εαand␈α4).␈αThe␈αprocess␈αis␈αabout␈αt␈α␈wice␈αas␈αhard␈αas␈αthe␈αabo␈α␈v␈α␈e␈αmethod␈αfor␈αin␈α␈tegers.
␈βT␈↓ ↓H␈ε∩Example␈α3.␈α→Con␈α␈v␈α␈ert␈εα␈α(.14159␈↓ ¬∂␈εα)␈↓ π9␈ε∩Example␈α4.␈α→Con␈α␈v␈α␈ert␈εα␈α(.110374␈↓ ∩␈εα)
␈βa␈↓ ¬≠␈ε¬10␈↓ ≡␈ε¬8
␈β␈␈↓ ↓H␈εαto␈αoctal.␈↓ π9␈εαto␈αdecimal.
␈β1␈↓ ↓L␈εα.␈↓ ↓Z␈εα1␈α∩4␈α∩1␈α∩5␈α∩9␈↓ π=␈εα.␈↓ πK␈εα1␈α∩1␈α∩0␈α∩3␈α∩7␈α∩4
␈β\␈↓ ↓}␈εα2␈α∩8␈α∩3␈α∩1␈α∩8␈ε⊗␈␈↓ πo␈εα2␈α∩2␈α∩0␈α∩7␈α∩7␈α∩0+
␈β
β␈↓ ↓Z␈∧
β↓Zα↓F␈↓ πK␈∧
βπKα↓j
␈β
⊂␈↓ ↓Z␈εα1␈↓ ↓p␈εα.␈↓ ↓}␈εα1␈α∩3␈α∩2␈α∩7␈α∩2␈↓ πK␈εα1␈↓ πa␈εα.␈↓ πo␈εα3␈α∩2␈α∩4␈α∩7␈α∩3␈α∩0
␈β
;␈↓ α"␈εα2␈α∩6␈α∩5␈α∩4␈α∩4␈ε⊗␈␈↓ λ∪␈εα6␈α∩5␈α∩1␈α∩6␈α∩6␈α∩0+
␈β
b␈↓ ↓}␈∧
b↓}α↓F␈↓ πo␈∧
bπoα↓j
␈β
o␈↓ ↓}␈εα1␈↓ α∀␈εα.␈↓ α"␈εα0␈α∩6␈α∩1␈α∩7␈α∩6␈↓ πo␈εα4␈↓ λ¬␈εα.␈↓ λ∪␈εα1␈α∩2␈α∩1␈α∩1␈α∩6␈α∩0
␈β∞~␈↓ αF␈εα1␈α∩2␈α∩3␈α∩5␈α∩2␈ε⊗␈␈↓ λ7␈εα2␈α∩4␈α∩2␈α∩3␈α∩4␈α∩0+
␈β∞A␈↓ α"␈∧∞Aα"α↓F␈↓ λ∪␈∧∞Aλ∪α↓j
␈β∞N␈↓ α"␈εα0␈↓ α8␈εα.␈↓ αF␈εα4␈α∩9␈α∩4␈α∩0␈α∩8␈↓ λ∪␈εα1␈↓ λ)␈εα.␈↓ λ7␈εα4␈α∩5␈α∩4␈α∩1␈α∩4␈α∩0
␈β∞z␈↓ αj␈εα9␈α∩8␈α∩8␈α∩1␈α∩6␈ε⊗␈␈↓ λ7␈εα1␈α∩1␈α∩3␈α∩0␈α∩3␈α∩0␈α∩0+
␈β∂ ␈↓ αF␈∧∂ αFα↓F␈↓ λ7␈∧∂ λ7α↓j
␈β∂-␈↓ αF␈εα3␈↓ α\␈εα.␈↓ αj␈εα9␈α∩5␈α∩2␈α∩4␈α∩6␈↓ λ7␈εα5␈↓ λM␈εα.␈↓ λ[␈εα6␈α∩7␈α∩1␈α∩7␈α∩0␈α∩0
␈β∂Y␈↓ αj␈εα1␈α∩9␈α∩0␈α∩5␈α∩2␈α∩8␈ε⊗␈␈↓ λ[␈εα1␈α∩5␈α∩6␈α∩3␈α∩6␈α∩0␈α∩0+
␈β∂␈␈↓ αj␈∧∂␈αjα↓F␈↓ λ[␈∧∂␈λ[α↓j
␈β⊂␈↓ αj␈εα7␈↓ β␈εα.␈↓ β∞␈εα6␈α∩2␈α∩1␈α∩1␈α∩2␈↓ λ[␈εα8␈↓ λq␈εα.␈↓ λ␈␈εα5␈α∩0␈α∩2␈α∩6␈α∩0␈α∩0
␈β⊂8␈↓ β∞␈εα1␈α∩2␈α∩4␈α∩2␈α∩2␈α∩4␈ε⊗␈␈↓ λ␈␈εα1␈α∩2␈α∩0␈α∩5␈α∩4␈α∩0␈α∩0+
␈β⊂↑␈↓ β∞␈∧⊂↑β∞α↓F␈↓ λ␈␈∧⊂↑λ␈α↓j
␈β⊂k␈↓ β∞␈εα4␈↓ β$␈εα.␈↓ β2␈εα9␈α∩6␈α∩8␈α∩9␈α∩6␈↓ λ␈␈εα6␈↓ 	∃␈εα.␈↓ 	#␈εα2␈α∩3␈α∩3␈α∩4␈α∩0␈α∩0
␈β⊃~␈↓ ↓H␈ε∂Answ␈α␈er:␈εα␈α(.110374␈↓ βY␈εα.␈αε.␈αε.␈↓ ∧	␈εα)␈↓ ∧#␈εα.␈↓ π9␈ε∂Answ␈α␈er:␈εα␈α(.141586␈↓ 	J␈εα.␈αε.␈αε.␈↓ 	z␈εα)
␈β⊃(␈↓ ∧∃␈ε¬8␈↓ 
ε␈ε¬10
␈β∪(

␈β↓Y␈↓ ↓H␈εα306␈↓ α=␈ε∞A␈α␈RITH␈α␈METIC␈εα␈↓ 
}4.4
␈βα(␈↓ ↓H␈ε∩D.␈α
Floating-poin␈α␈t␈α
con␈α␈v␈α␈ersion.␈εα␈α∃When␈α
⎇oating-poin␈α␈t␈α
values␈α
are␈αto␈α
be␈α
con␈α␈v␈α␈erted,␈α
it
␈βαS␈↓ ↓H␈εαis␈αλnecessary␈αλto␈αλdeal␈αλwith␈αλboth␈αλthe␈αλexponen␈α␈t␈αλand␈αλthe␈αλfraction␈αλparts␈αλsim␈α␈ultaneously,
␈βα}␈↓ ↓H␈εαsince␈αcon␈α␈v␈α␈ersion␈αof␈αthe␈αexponen␈α␈t␈αwill␈αa{ect␈αthe␈αfraction␈αpart.␈αGiv␈α␈en␈αthe␈αn␈α␈um␈α␈ber
␈ββ%␈↓ α∧␈εe␈↓ πf␈εe␈↓ 
⊃␈εE
␈ββ*␈↓ ↓H␈ελf␈↓ ↓`␈ε⊗↓␈↓ ↓r␈εα2␈↓ α≠␈εαto␈αbe␈αcon␈α␈v␈α␈erted␈αto␈αdecimal,␈αw␈α␈e␈αmay␈αexpress␈↓ πT␈εα2␈↓ π}␈εαin␈αthe␈αform␈↓ 	:␈ελF␈↓ 	[␈ε⊗↓␈εα␈αλ1␈↓ 	␈␈εα0␈↓ 
0␈εα(usually
␈ββU␈↓ ↓H␈εαby␈α∞means␈α∂of␈α∞auxiliary␈α∂tables),␈α∂and␈α∞then␈α∂con␈α␈v␈α␈ert␈↓ πV␈ελF␈↓ πp␈ελf␈↓ λ∂␈εαto␈α∂decimal.␈α∪Alternativ␈α␈ely,
␈β∧␈↓ ↓H␈εαw␈α␈e␈α
can␈αm␈α␈ultiply␈↓ βL␈ελe␈↓ βe␈εαby␈↓ ∧_␈εαlog␈↓ ∧h␈εα2␈αand␈αround␈αthis␈α
to␈αthe␈αnearest␈αin␈α␈teger␈↓ 	M␈ελE␈↓ 	g␈εα;␈αthen␈α
divide
␈β∧⊃␈↓ ∧F␈ε¬10
␈β∧&␈↓ α∧␈εe␈↓ αs␈εE␈↓ 
=␈εE
␈β∧+␈↓ ↓H␈ελf␈↓ ↓`␈ε⊗↓␈↓ ↓r␈εα2␈↓ α≤␈εαby␈α1␈↓ αa␈εα0␈↓ β∪␈εαand␈αcon␈α␈v␈α␈ert␈αthe␈αresult.␈αCon␈α␈v␈α␈ersely,␈αgiv␈α␈en␈αthe␈αn␈α␈um␈α␈ber␈↓ 	f␈ελF␈↓ 
π␈ε⊗↓␈εα␈αλ1␈↓ 
+␈εα0␈↓ 
]␈εαto␈αbe
␈β∧V␈↓ ↓H␈εαcon␈α␈v␈α␈erted␈α	to␈α	binary,␈α
w␈α␈e␈α	may␈α	con␈α␈v␈α␈ert␈↓ ε	␈ελF␈↓ ε+␈εαand␈α	then␈α
m␈α␈ultiply␈α	it␈α	by␈α	the␈α	⎇oating-poin␈α␈t
␈β∧⎇␈↓ αl␈εE
␈β¬α␈↓ ↓H␈εαn␈α␈um␈α␈ber␈α
1␈↓ αZ␈εα0␈↓ β
␈εα(again␈α
by␈α
using␈α
auxiliary␈α
tables).␈αObvious␈α
techniques␈α
can␈α
be␈α
used␈α	to
␈β¬-␈↓ ↓H␈εαreduce␈α
the␈α
maxim␈α␈um␈αsize␈α
of␈α
the␈αauxiliary␈α
tables␈α
by␈αusing␈α
sev␈α␈eral␈α
m␈α␈ultiplications
␈β¬X␈↓ ↓H␈εαand/or␈αdivisions,␈αalthough␈αthis␈αcan␈αcause␈αrounding␈αerrors␈αto␈αpropagate.
␈βε&␈↓ ↓H␈ε∩E.␈α
Multiple-precision␈αcon␈α␈v␈α␈ersion.␈εα␈α∃When␈αcon␈α␈v␈α␈erting␈αm␈α␈ultiprecision␈α
n␈α␈um␈α␈bers,␈αit␈α
is
␈βεQ␈↓ ↓H␈εαmost␈α∞con␈α␈v␈α␈enien␈α␈t␈α∞to␈α∞start␈α∞by␈α∞con␈α␈v␈α␈erting␈α∞blocks␈α∞of␈α∞digits,␈α∂which␈α∞can␈α∞be␈α∞handled
␈βε|␈↓ ↓H␈εαby␈α
single-precision␈α
techniques,␈α
and␈αthen␈α
to␈α
com␈α␈bine␈α
these␈α
blocks␈α
by␈α
using␈α
simple
␈βπ#␈↓ λd␈εn
␈βπ(␈↓ ↓H␈εαm␈α␈ultiple-precision␈αλtechniques.␈α
For␈αλexample,␈α	suppose␈αλthat␈αλ1␈↓ λR␈εα0␈↓ λ}␈εαis␈αλthe␈αλhighest␈αλpo␈α␈w␈α␈er
␈βπS␈↓ ↓H␈εαof␈α10␈αless␈αthan␈αthe␈αcomputer␈αw␈α␈ord␈αsize.␈αThen
␈βλ⊂␈↓ ↓b␈εαa)␈↓ α␈εαTo␈α⊂con␈α␈v␈α␈ert␈α⊂a␈α⊂m␈α␈ultiple-precision␈ε∂␈α⊃in␈α␈teger␈εα␈α⊂from␈α⊂binary␈α⊂to␈α⊂decimal,␈α⊃divide␈α⊂it
␈βλ≤␈↓ βr␈ε↓␈␈↓ ∀␈ε↓↓
␈βλ6␈↓ βS␈εn␈↓ λ}␈εn
␈βλ<␈↓ ↓H␈εαrepeatedly␈α
by␈α∞1␈↓ βA␈εα0␈↓ ∧␈εαth␈α␈us␈α∞con␈α␈v␈α␈erting␈α
from␈α∞binary␈α
to␈α∞radix␈α
1␈↓ λl␈εα0␈↓ 	≥␈εαby␈α∞Method␈α
(1a)␈↓ "␈εα.
␈βλg␈↓ ↓H␈εαSingle-precision␈α∞operations␈α∂will␈α∂giv␈α␈e␈α∞the␈↓ εP␈ελn␈↓ εt␈εαdecimal␈α∂digits␈α∂for␈α∞each␈α∂place␈α∂of␈α∞the
␈β	
␈↓ αJ␈εn
␈β	∩␈↓ ↓H␈εαradix-1␈↓ α8␈εα0␈↓ αh␈εαrepresen␈α␈tation.
␈β	?␈↓ ↓`␈εαb)␈↓ α␈εαTo␈α⊂con␈α␈v␈α␈ert␈α⊃a␈α⊂m␈α␈ultiple-precision␈ε∂␈α⊂fraction␈εα␈α⊂from␈α⊃binary␈α⊂to␈α⊂decimal,␈α⊃proceed
␈β	K␈↓ ¬≥␈ε↓␈␈↓ 	q␈ε↓↓
␈β	e␈↓ ∧␈␈εn␈↓ 	←␈εn
␈β	j␈↓ ↓H␈εαsimilarly,␈αm␈α␈ultiplying␈αby␈α1␈↓ ∧m␈εα0␈↓ ¬+␈εαi.e.,␈αusing␈αMethod␈α(2a)␈αwith␈↓ λk␈ελB␈↓ 	
␈εα=␈α
1␈↓ 	M␈εα0␈↓ 	␈␈εα.
␈β
↔␈↓ ↓d␈εαc)␈↓ α␈εαTo␈απcon␈α␈v␈α␈ert␈απa␈αεm␈α␈ultiple-precision␈απin␈α␈teger␈απfrom␈αεdecimal␈απto␈απbinary,␈αλcon␈α␈v␈α␈ert␈αεblocks
␈β
=␈↓ εs␈εn
␈β
C␈↓ ↓H␈εαof␈↓ ↓r␈ελn␈↓ α∪␈εαdigits␈α|rst;␈αthen␈αcon␈α␈v␈α␈ert␈αfrom␈αradix␈α1␈↓ εa␈εα0␈↓ π⊃␈εαto␈αbinary␈αby␈αusing␈αMethod␈α(1b).
␈β
p␈↓ ↓`␈εαd)␈↓ α␈εαFinally,␈αa␈αm␈α␈ultiple-precision␈αfraction␈αmay␈αbe␈αcon␈α␈v␈α␈erted␈αfrom␈αdecimal␈αto␈αbi-
␈β≠␈↓ ↓H␈εαnary␈αby␈αa␈αtechnique␈αsimilar␈αto␈α(c),␈αusing␈αMethod␈α(2b).
␈βi␈↓ ↓H␈ε∩F.␈αHistory␈αand␈αBibliograph␈α␈y.␈εα␈α_Radix-con␈α␈v␈α␈ersion␈αtechniques␈αimplicitly␈αoriginated
␈β∀␈↓ ↓H␈εαin␈αεancien␈α␈t␈απproblems␈απdealing␈αεwith␈απw␈α␈eigh␈α␈ts,␈αλmeasures,␈αλand␈αεcurrencies,␈αλwhen␈απa␈αεmix␈α␈ed-
␈β?␈↓ ↓H␈εαradix␈α∞system␈α∞was␈α∞generally␈α∞in␈α␈v␈α␈olv␈α␈ed.␈α∩Auxiliary␈α∞tables␈α∞w␈α␈ere␈α∞usually␈α∞used␈α∞as␈α∞an
␈βj␈↓ ↓H␈εαaid␈α∞to␈α∂con␈α␈v␈α␈ersion.␈α∪During␈α∞the␈α∂sev␈α␈en␈α␈teen␈α␈th␈α∞cen␈α␈tury␈α∂when␈α∞sexagesimal␈α∞fractions
␈β
⊗␈↓ ↓H␈εαw␈α␈ere␈α
being␈αsupplan␈α␈ted␈α
by␈αdecimal␈αfractions,␈α
it␈αwas␈αnecessary␈α
to␈αcon␈α␈v␈α␈ert␈α
bet␈α␈w␈α␈een
␈β
A␈↓ ↓H␈εαthe␈α∞t␈α␈w␈α␈o␈α∞systems␈α∞in␈α∞order␈α∞to␈α∞use␈α∂existing␈α∞books␈α∞of␈α∞tables;␈α∂a␈α∞systematic␈α∞method
␈β
l␈↓ ↓H␈εαto␈α∂transform␈α⊂fractions␈α∂from␈α⊂radix␈α∂60␈α⊂to␈α∂radix␈α⊂10␈α∂and␈α∂vice␈α⊂v␈α␈ersa␈α∂was␈α⊂giv␈α␈en␈α∂in
␈β∞↔␈↓ ↓H␈εαthe␈α
1667␈α
edition␈α
of␈α
William␈α
Ough␈α␈tred's␈ε∂␈α
Clavis␈α
Mathematic≤␈εα,␈αChapter␈α
6,␈α
Section
␈β∞B␈↓ ↓H␈εα18.␈α⊗(This␈α∂material␈α∂was␈α⊂not␈α∂presen␈α␈t␈α∂in␈α⊂the␈α∂original␈α∂1631␈α⊂edition␈α∂of␈α∂Ough␈α␈tred's
␈β∞n␈↓ ↓H␈εαbook.)␈α→Con␈α␈v␈α␈ersion␈α⊃rules␈α⊂had␈α⊃been␈α⊃giv␈α␈en␈α⊂already␈α⊃by␈α⊂al-Kash␈↓ 	⊗␈εα∂␈↓ 	~␈εα␈↓ 	5␈εαof␈α⊂Persia␈α⊃in␈α⊂his
␈β∂→␈↓ ↓H␈ε∂Key␈αto␈α
Arithmetic␈εα␈α
(c.␈α∂1414),␈α
where␈αMethods␈α
(1a),␈α
(1b),␈α
and␈α
(2a)␈α
are␈α
clearly␈αex-
␈β∂D␈↓ ↓H␈εαplained␈α
[␈ε∂Istorik␈α␈o-Mat.␈α∞Issled.␈ε∩␈α∞7␈εα␈α∞(1954),␈α∞126↑135],␈α∞but␈α∞his␈α
w␈α␈ork␈α∞was␈α∞unkno␈α␈wn␈α
in
␈β∂o␈↓ ↓H␈εαEurope.␈αThe␈α18th␈αcen␈α␈tury␈αAmerican␈αmathematician␈αHugh␈αJones␈αused␈αthe␈αw␈α␈ords
␈β⊂~␈↓ ↓H␈εα\octavation"␈α∂and␈α⊂\decimation"␈α⊂to␈α⊂describe␈α∂octal/decimal␈α⊂con␈α␈v␈α␈ersions,␈α⊃but␈α∂his
␈β⊂F␈↓ ↓H␈εαmethods␈α⊂w␈α␈ere␈α∂not␈α⊂as␈α⊂clev␈α␈er␈α⊂as␈α⊂his␈α⊂terminology.␈α_A.␈α⊂M.␈α⊂Legendre␈α⊂[␈ε∂Th␈↓ 
 ␈ε∂∞␈↓ 
!␈ε∂e␈↓ 
1␈ε∂orie␈α∂des
␈β⊂q␈↓ ↓H␈ε∂nom␈α␈bres␈εα␈α⊂(Paris,␈α∩1798),␈α⊃229]␈α⊃noted␈α⊂that␈α⊃positiv␈α␈e␈α⊂in␈α␈tegers␈α⊃may␈α⊂be␈α⊂con␈α␈v␈α␈enien␈α␈tly
␈β⊃≤␈↓ ↓H␈εαcon␈α␈v␈α␈erted␈αto␈αbinary␈αform␈αif␈αthey␈αare␈αrepeatedly␈αdivided␈αby␈α64.
␈β∪(

␈β↓Y␈↓ ↓H␈εα4.4␈ε∞␈↓ λ~R␈α↓A␈α␈DIX␈α	CONV␈α␈ERSION␈↓ 
v␈εα307
␈βα(␈↓ α␈εαIn␈α
1946,␈αH.␈α
H.␈α
Goldstine␈αand␈α
J.␈α
v␈α␈on␈αNeumann␈α
gav␈α␈e␈α
prominen␈α␈t␈α
consideration
␈βαS␈↓ ↓H␈εαto␈α
radix␈α
con␈α␈v␈α␈ersion␈α
in␈αtheir␈α
classic␈α
memoir,␈α∞\Planning␈α
and␈α
coding␈αproblems␈α
for
␈βα}␈↓ ↓H␈εαan␈α
electronic␈αcomputing␈α
instrumen␈α␈t,"␈αbecause␈α
it␈αwas␈α
necessary␈αto␈α
justify␈αthe␈α
use
␈ββ*␈↓ ↓H␈εαof␈α∂binary␈α∂arithmetic;␈α⊃see␈α∂John␈α∂v␈α␈on␈α⊂Neumann,␈ε∂␈α⊂Collected␈α∂Works␈ε∩␈α∂5␈εα␈α∂(New␈α∂York:
␈ββU␈↓ ↓H␈εαMacmillan,␈α
1963),␈α
127↑142.␈α∞Another␈α
early␈α
discussion␈α
of␈α
radix␈α
con␈α␈v␈α␈ersion␈α
on␈αbi-
␈β∧␈↓ ↓H␈εαnary␈απcomputers␈αλwas␈αλpublished␈αλby␈αλF.␈αλKoons␈αλand␈απS.␈αλLubkin,␈ε∂␈α	Math.␈αλComp.␈ε∩␈αλ3␈εα␈απ(1949),
␈β∧+␈↓ ↓H␈εα427↑431,␈α	who␈α	suggested␈α	a␈α	rather␈αλun␈α␈usual␈α	method.␈αThe␈α	|rst␈α	discussion␈α	of␈αλ⎇oating-
␈β∧V␈↓ ↓H␈εαpoin␈α␈t␈αλcon␈α␈v␈α␈ersion␈α	was␈α	giv␈α␈en␈α	somewhat␈α	later␈α	by␈αλF.␈α	L.␈α	Bauer␈α	and␈α	K.␈α	Samelson␈αλ[␈ε∂Zeit.
␈β¬α␈↓ ↓H␈ε∂f␈↓ ↓T␈ε∂u␈↓ ↓U␈ε∂∪␈↓ ↓h␈ε∂r␈αangewandte␈αMath.␈αund␈αPh␈α␈ysik␈ε∩␈α4␈εα␈α(1953),␈α312↑316].
␈β¬-␈↓ α␈εαThe␈αfollo␈α␈wing␈α
articles␈αmay␈α
be␈αuseful␈αfor␈α
further␈αreference:␈α
A␈αnote␈α
by␈αG.␈αT.
␈β¬X␈↓ ↓H␈εαLak␈α␈e␈α
[␈ε∂CA␈α␈CM␈ε∩␈α5␈εα␈α
(1962),␈α468↑469]␈αmen␈α␈tions␈α
some␈αhardware␈α
techniques␈αfor␈α
con␈α␈v␈α␈er-
␈βεβ␈↓ ↓H␈εαsion␈αand␈α
giv␈α␈es␈αclear␈α
examples.␈α
A.␈α
H.␈αStroud␈α
and␈αD.␈αSecrest␈α
[␈ε∂Comp.␈αJ.␈ε∩␈α
6␈εα␈α(1963),
␈βε.␈↓ ↓H␈εα62↑66]␈α∂hav␈α␈e␈α⊂discussed␈α⊂con␈α␈v␈α␈ersion␈α∂of␈α⊂m␈α␈ultiple-precision␈α⊂⎇oating-poin␈α␈t␈α∂n␈α␈um␈α␈bers.
␈βεZ␈↓ ↓H␈εαThe␈αcon␈α␈v␈α␈ersion␈α
of␈ε∂␈αunnormalized␈εα␈α
⎇oating-poin␈α␈t␈α
n␈α␈um␈α␈bers,␈αpreserving␈α
the␈αamoun␈α␈t
␈βπ¬␈↓ ↓H␈εαof␈α
\signi|cance"␈α
implied␈α	by␈α
the␈α
represen␈α␈tation,␈αhas␈α
been␈α
discussed␈α
by␈α	H.␈α
Kanner
␈βπ0␈↓ ↓H␈εα[␈ε∂JA␈α␈CM␈ε∩␈α12␈εα␈α
(1965),␈α242↑246]␈α
and␈αby␈α
N.␈αMetropolis␈α
and␈αR.␈αL.␈α
Ashenh␈α␈urst␈α[␈ε∂Math.
␈βπ[␈↓ ↓H␈ε∂Comp.␈ε∩␈α	19␈εα␈α
(1965),␈α
435↑441].␈αSee␈α	also␈α
K.␈α
Sikdar,␈ε∂␈α
Sankh␈α␈y␈↓ λ≥␈ε∂∩␈↓ λ≥␈ε∂a␈↓ λ9␈εαseries␈α
B,␈ε∩␈α	30␈εα␈α
(1968),␈α
315↑
␈βλε␈↓ ↓H␈εα334,␈αand␈αthe␈αreferences␈αhe␈αcites.
␈βλ␈␈↓ ↓H␈ε≥E␈α␈XERCI␈α↓SE␈α␈S
␈β	C␈↓ ↓;␈ε↓x
␈β	G␈↓ ↓g␈ε∪1.␈↓ α␈εβ[␈ε	25␈↓ α;␈εβ]␈α⊗Gen␈α␈eralize␈απMeth␈α␈od␈απ(1␈α␈b)␈απso␈απtha␈α␈t␈αλit␈απwo␈α␈rks␈απwith␈απarb␈α␈i␈α↓t␈α␈rary␈απmix␈α}ed-ra␈α␈dix␈απno␈α␈tation␈α␈s,
␈β	o␈↓ ↓H␈εβc␈α␈on␈α␈v␈α}erting
␈β
1␈↓ ↓␈␈ε	a␈↓ α&␈ε	b␈↓ αu␈εβ.␈αε.␈α¬.␈↓ β!␈ε	b␈↓ β:␈ε	b␈↓ βZ␈εβ+␈↓ ∧β␈ε↔↓␈α¬↓␈αε↓␈↓ ∧1␈εβ+␈↓ ∧Z␈ε	a␈↓ ∧v␈ε	b␈↓ ¬⊗␈εβ+␈↓ ¬>␈ε	a␈↓ ¬␈␈εβin␈α}to␈↓ ε[␈ε	A␈↓ π␈ε	B␈↓ πd␈εβ.␈αε.␈αε.␈↓ λ⊃␈ε	B␈↓ λ1␈ε	B␈↓ λX␈εβ+␈↓ 	↓␈ε↔↓␈α¬↓␈αε↓␈↓ 	/␈εβ+␈↓ 	X␈ε	A␈↓ 	y␈ε	B␈↓ 
!␈εβ+␈↓ 
J␈ε	A␈↓ 
k␈εβ,
␈β
<␈↓ α∂␈εm␈↓ α2␈εm␈↓ αJ␈ε~␈␈εε1␈↓ β-␈εε1␈↓ βF␈εε0␈↓ ∧i␈εε1␈↓ ¬α␈εε0␈↓ ¬N␈εε0␈↓ εp␈εM␈↓ π≡␈εM␈↓ π9␈ε~␈␈εε1␈↓ λ$␈εε1␈↓ λD␈εε0␈↓ 	m␈εε1␈↓ 

␈εε0␈↓ 
←␈εε0
␈β
t␈↓ ↓H␈εβwh␈α␈ere␈α0␈ε↔␈α	∀␈↓ αl␈ε	a␈↓ β⊃␈εβ<␈↓ β<␈ε	b␈↓ βT␈εβ,␈α0␈ε↔␈α	∀␈↓ ∧-␈ε	A␈↓ ∧Z␈εβ<␈↓ ¬¬␈ε	B␈↓ ¬3␈εβfor␈α0␈ε↔␈α	∀␈↓ ε+␈ε	j␈↓ εC␈εβ<␈↓ εn␈ε	m␈↓ π␈εβ,␈α0␈ε↔␈α	∀␈↓ πd␈ε	J␈↓ λ↓␈εβ<␈↓ λ+␈ε	M␈↓ λN␈εβ.
␈β
}␈↓ α|␈εj␈↓ βH␈εj␈↓ ∧B␈εJ␈↓ ¬_␈εJ
␈β≠␈↓ α␈εβGiv␈α␈e␈αan␈αexa␈α␈mple␈αof␈α
y␈α␈o␈α␈ur␈αgen␈α␈eralization␈αb␈α␈y␈α
ma␈α␈n␈α␈u␈α␈ally␈α
co␈α␈n␈α␈v␈α}erting␈αthe␈αqu␈α␈an␈α␈tity␈α\3
␈βC␈↓ ↓H␈εβd␈α␈ay␈α␈s,␈α⊂9␈α∞hou␈α␈rs,␈α⊂1␈α␈2␈α∂min␈α}utes,␈α∂and␈α∞3␈α␈7␈α∂se␈α␈con␈α␈ds"␈α∞in␈α␈to␈α∞l␈α↓o␈α␈ng␈α∞ton␈α␈s,␈α⊂h␈α␈u␈α␈nd␈α␈red␈α␈w␈α␈eigh␈α␈ts,␈α∂ston␈α␈es,
␈βk␈↓ ↓H␈εβp␈α␈ou␈α␈nd␈α␈s,␈α
an␈α␈d␈αou␈α␈nc␈α␈es.␈α∂(Let␈α
o␈α␈ne␈αsec␈α␈on␈α␈d␈αequ␈α␈al␈αone␈αo␈α␈un␈α␈ce.␈α∂Th␈α␈e␈α
British␈αsy␈α␈stem␈αof␈αw␈α␈eigh␈α␈t␈α␈s
␈β∩␈↓ ↓H␈εβh␈α␈as␈αλ1␈α	sto␈α␈ne␈αλ=␈α
1␈α␈4␈α	p␈α␈ou␈α␈nd␈α␈s,␈α
1␈αλh␈α␈u␈α␈nd␈α␈red␈α␈we␈α␈i␈α↓g␈α␈h␈α␈t␈αλ=␈α
8␈αλsto␈α␈ne,␈α	1␈α	lon␈α␈g␈αλton␈αλ=␈α	20␈αλh␈α␈u␈α␈nd␈α␈redw␈α␈eigh␈α}t.)
␈β:␈↓ ↓H␈εβIn␈α
o␈α␈ther␈α
w␈α␈ord␈α␈s,␈α∞let␈↓ βj␈ε	b␈↓ ∧∂␈εβ=␈α∞6␈α␈0,␈↓ ∧v␈ε	b␈↓ ¬≤␈εβ=␈α
60␈α␈,␈↓ εα␈ε	b␈↓ ε(␈εβ=␈α
24,␈↓ π∂␈ε	m␈↓ π9␈εβ=␈α∞3␈α␈,␈↓ λ∂␈ε	B␈↓ λ<␈εβ=␈α∞1␈α␈6,␈↓ 	#␈ε	B␈↓ 	P␈εβ=␈α∞1␈α␈4,␈↓ 
7␈ε	B␈↓ 
d␈εβ=␈α∞8␈α␈,
␈βD␈↓ βv␈εε0␈↓ ¬α␈εε1␈↓ ε∂␈εε2␈↓ λ#␈εε0␈↓ 	7␈εε1␈↓ 
K␈εε2
␈βa␈↓ ↓H␈ε	B␈↓ ↓u␈εβ=␈α∞20␈α␈,␈↓ α]␈ε	M␈↓ β
␈εβ=␈α∞4␈α␈;␈α∂the␈α
pro␈α␈blem␈α
i␈α↓s␈α
to␈α∞|␈α␈nd␈↓ ε9␈ε	A␈↓ ε[␈εβ,␈↓ εr␈εβ.␈αε.␈αε.␈↓ π≡␈εβ,␈↓ π6␈ε	A␈↓ πf␈εβin␈α
th␈α␈e␈α∞p␈α␈rop␈α␈er␈α∞ra␈α␈nge␈α␈s␈α∞su␈α␈ch␈α
tha␈α␈t
␈βl␈↓ ↓[␈εε3␈↓ εN␈εε4␈↓ πK␈εε0
␈β
	␈↓ ↓H␈εβ3␈↓ ↓X␈ε	b␈↓ ↓q␈ε	b␈↓ α
␈ε	b␈↓ α+␈εβ+␈α	2␈↓ αf␈ε	b␈↓ α}␈ε	b␈↓ β ␈εβ+␈α	12␈↓ βk␈ε	b␈↓ ∧
␈εβ+␈α	37␈α=␈↓ ¬∀␈ε	A␈↓ ¬6␈ε	B␈↓ ¬V␈ε	B␈↓ ¬v␈ε	B␈↓ ε⊗␈ε	B␈↓ ε>␈εβ+␈↓ εi␈ε	A␈↓ π␈ε	B␈↓ π+␈ε	B␈↓ πK␈ε	B␈↓ πs␈εβ+␈↓ λ≡␈ε	A␈↓ λ@␈ε	B␈↓ λ`␈ε	B␈↓ 	λ␈εβ+␈↓ 	3␈ε	A␈↓ 	U␈ε	B␈↓ 	⎇␈εβ+␈↓ 
(␈ε	A␈↓ 
I␈εβ,␈α∂u␈α␈sing
␈β
∀␈↓ ↓d␈εε2␈↓ ↓⎇␈εε1␈↓ α⊗␈εε0␈↓ αr␈εε1␈↓ β␈εε0␈↓ βw␈εε0␈↓ ¬)␈εε4␈↓ ¬I␈εε3␈↓ ¬i␈εε2␈↓ ε	␈εε1␈↓ ε)␈εε0␈↓ ε}␈εε3␈↓ π≡␈εε2␈↓ π>␈εε1␈↓ π↑␈εε0␈↓ λ3␈εε2␈↓ λS␈εε1␈↓ λs␈εε0␈↓ 	H␈εε1␈↓ 	h␈εε0␈↓ 
=␈εε0
␈β
1␈↓ ↓H␈εβa␈αsy␈α␈stema␈α␈ti␈α↓c␈αme␈α␈thod␈αt␈α␈hat␈αgen␈α␈era␈α␈l␈α↓izes␈αMe␈α␈tho␈α␈d␈α(␈α↓1␈α␈b).␈α∂(␈α↓All␈α
a␈α␈rithme␈α␈ti␈α↓c␈αis␈α
to␈αb␈α␈e␈α
d␈α␈on␈α␈e␈α
in␈αa
␈β
X␈↓ ↓H␈εβm␈α␈i␈α↓x␈α}ed-ra␈α␈dix␈αsy␈α␈stem␈α␈.␈α↓)
␈β∞	␈↓ ↓g␈ε∪2.␈↓ α␈εβ[␈ε	25␈↓ α;␈εβ]␈α⊗Gen␈α␈eralize␈α
Meth␈α␈od␈α
(1a␈α␈)␈α∞so␈α
tha␈α␈t␈α∞it␈α∞w␈α␈o␈α␈rks␈α
wi␈α↓th␈α
m␈α␈i␈α↓x␈α}ed-ra␈α␈dix␈α
no␈α␈tation␈α␈s,␈α∂a␈α␈s␈α∞in
␈β∞1␈↓ ↓H␈εβe␈α␈x␈α␈ercise␈α1,␈α
a␈α␈nd␈αg␈α␈iv␈α␈e␈αan␈αex␈α␈am␈α␈ple␈αof␈α
y␈α}ou␈α␈r␈α
g␈α␈ene␈α␈ralization␈αb␈α␈y␈αma␈α␈n␈α␈u␈α␈all␈α↓y␈αs␈α␈olving␈αth␈α␈e␈αsame
␈β∞X␈↓ ↓H␈εβc␈α␈on␈α␈v␈α}ersion␈α
prob␈α␈lem␈αsta␈α␈ted␈αin␈αe␈α␈x␈α␈ercise␈α1␈α␈.
␈β∂¬␈↓ ↓;␈ε↓x
␈β∂	␈↓ ↓g␈ε∪3.␈↓ α␈εβ[␈ε	25␈↓ α;␈εβ]␈α⊗(D.␈α
Taran␈α}to.)␈α⊗When␈α	frac␈α␈ti␈α↓o␈α␈ns␈α
a␈α␈re␈α
b␈α␈eing␈α	con␈α}v␈α␈erte␈α␈d,␈α
ther␈α␈e␈α
is␈α
in␈α
g␈α␈ener␈α␈al␈α
no␈α	ob␈α␈-
␈β∂1␈↓ ↓H␈εβv␈α␈ious␈αεway␈αεto␈αεd␈α␈ecide␈αεh␈α␈o␈α␈w␈απm␈α␈an␈α␈y␈αεd␈α␈igits␈απto␈αεg␈α␈i␈α↓v␈α}e␈αεi␈α↓n␈αεth␈α␈e␈αεans␈α␈we␈α␈r.␈α
Design␈αεa␈αεsimp␈α␈l␈α↓e␈αεg␈α␈ener␈α␈ali␈α↓z␈α␈ation
␈β∂X␈↓ ↓H␈εβo␈α␈f␈α∂Meth␈α␈od␈α∞(2a␈α␈)␈α∂tha␈α␈t,␈α⊂giv␈α␈e␈α␈n␈α∂t␈α␈w␈α␈o␈α∞po␈α␈si␈α↓tiv␈α}e␈α∂rad␈α␈ix-␈↓ π␈ε	b␈↓ π≤␈εβfrac␈α␈ti␈α↓o␈α␈ns␈↓ λ(␈ε	u␈↓ λK␈εβan␈α␈d␈↓ 	⊂␈ε	∂␈↓ 	+␈εβbet␈α␈w␈α␈ee␈α␈n␈α∂0␈α∞an␈α␈d␈α∂1␈α␈,
␈β⊂␈↓ ↓H␈εβc␈α␈on␈α␈v␈α}erts␈↓ αM␈ε	u␈↓ αn␈εβto␈α
a␈α
ro␈α␈un␈α␈ded␈αrad␈α␈i␈α↓x␈α␈-␈↓ ¬⊃␈ε	B␈↓ ¬5␈εβe␈α␈quiv␈α␈alen␈α␈t␈↓ εW␈ε	U␈↓ ε␈␈εβth␈α␈at␈α
ha␈α␈s␈α
just␈α
en␈α␈ou␈α␈gh␈α
p␈α␈laces␈↓ 
$␈ε	M␈↓ 
S␈εβto␈α
the
␈β⊂'␈↓ ↓H␈εβrig␈α␈h␈α␈t␈α
of␈α
th␈α␈e␈α
rad␈α␈ix␈α
p␈α␈oin␈α␈t␈α
to␈αensu␈α␈re␈α
th␈α␈at␈ε↔␈α
j␈↓ ε⊗␈ε	U␈↓ ε:␈ε↔␈␈↓ εd␈ε	u␈↓ εx␈ε↔j␈εβ␈α
<␈↓ π<␈ε	∂␈↓ πH␈εβ.␈α∩[In␈αpar␈α␈ti␈α↓c␈α␈ular␈α
if␈↓ 	S␈ε	u␈↓ 	t␈εβis␈α
a␈α
m␈α␈u␈α␈l␈α↓tip␈α␈l␈α↓e
␈β⊂K␈↓ ↓⎇␈ε~␈␈↓ α⊗␈εm␈↓ βM␈ε~␈␈↓ βf␈εm
␈β⊂O␈↓ ↓H␈εβo␈α␈f␈↓ ↓p␈ε	b␈↓ α9␈εβand␈↓ α{␈ε	∂␈↓ β∪␈εβ=␈↓ β?␈ε	b␈↓ β⎇␈εβ/2␈α␈,␈α
th␈α␈e␈αvalu␈α␈e␈αof␈↓ ¬p␈ε	U␈↓ ε↔␈εβwi␈α↓ll␈αha␈α␈v␈α␈e␈αjust␈αe␈α␈nou␈α␈gh␈αdigits␈αso␈αth␈α␈at␈↓ 
-␈ε	u␈↓ 
M␈εβcan␈αbe
␈β⊂s␈↓ ≤␈εε1
␈β⊂w␈↓ ↓H␈εβre␈α␈comp␈α␈ute␈α␈d␈α	exa␈α␈ctly,␈α
g␈α␈i␈α↓v␈α}en␈↓ ∧N␈ε	U␈↓ ∧s␈εβa␈α␈nd␈↓ ¬2␈ε	m␈↓ ¬O␈εβ.␈αNote␈α	th␈α␈at␈↓ εy␈ε	M␈↓ π%␈εβmigh␈α␈t␈α	be␈α	ze␈α␈ro;␈α
for␈α
e␈α␈xa␈α␈mple,␈α
if␈↓ 
X␈ε	∂␈↓ 
n␈ε↔∀
␈β⊃¬␈↓ ≤␈∧⊃¬≤α
␈β⊃π␈↓ ≤␈εε2
␈β⊃≡␈↓ ↓H␈εβa␈α␈nd␈↓ αλ␈ε	u␈↓ α&␈εβ>␈α	1␈ε↔␈απ␈␈↓ β⊃␈ε	∂␈↓ β≡␈εβ,␈αthe␈αp␈α␈rop␈α␈er␈αan␈α␈sw␈α␈er␈αis␈↓ ¬d␈ε	U␈↓ ε	␈εβ=␈α	1.]
␈β∪(

␈β↓Y␈↓ ↓H␈εα308␈↓ α=␈ε∞A␈α␈RITH␈α␈METIC␈εα␈↓ 
}4.4
␈βα*␈↓ ↓g␈ε∪4.␈↓ α␈εβ[␈ε	M21␈↓ αX␈εβ]␈α⊗(a)␈απPro␈α␈v␈α}e␈απth␈α␈at␈απev␈α}ery␈αεreal␈απn␈α␈u␈α␈m␈α␈b␈α␈er␈απha␈α␈ving␈αεa␈απte␈α␈rminatin␈α␈g␈ε⊂␈απb␈α␈i␈α↓n␈α␈ary␈εβ␈αεrep␈α␈resen␈α}tation
␈βαR␈↓ ↓H␈εβa␈α␈l␈α↓s␈α␈o␈α∂has␈α∂a␈α∂te␈α␈rminat␈α␈i␈α↓n␈α␈g␈ε⊂␈α∂de␈α␈cimal␈εβ␈α∂repre␈α␈sen␈α␈ta␈α␈tion.␈α!(b)␈α∂Fi␈α↓n␈α␈d␈α∂a␈α∂simp␈α␈le␈α∂con␈α␈dition␈α∂o␈α␈n␈α∂the
␈βαy␈↓ ↓H␈εβp␈α␈ositiv␈α␈e␈αin␈α␈teg␈α␈ers␈↓ βA␈ε	b␈↓ β[␈εβa␈α␈nd␈↓ ∧≥␈ε	B␈↓ ∧@␈εβth␈α␈at␈α
is␈α
sa␈α␈tis|ed␈αif␈α
an␈α␈d␈αon␈α␈l␈α↓y␈αif␈α
ev␈α}ery␈αreal␈αn␈α␈um␈α}ber␈αtha␈α␈t␈α
ha␈α␈s␈α
a
␈ββ!␈↓ ↓H␈εβte␈α␈rmina␈α␈ti␈α↓n␈α␈g␈αrad␈α␈ix-␈↓ βT␈ε	b␈↓ βl␈εβrep␈α␈resen␈α␈t␈α␈ation␈αa␈α␈lso␈αha␈α␈s␈αa␈αtermin␈α␈ating␈α
radix␈α␈-␈↓ λk␈ε	B␈↓ 	
␈εβrep␈α␈resen␈α}tation␈α␈.
␈ββQ␈↓ 
w␈εn
␈ββR␈↓ 	n␈ε∃LD␈α␈X␈α∃=␈↓ π␈ε∃=
␈ββU␈↓ ↓g␈ε∪5.␈↓ α␈εβ[␈ε	M20␈↓ αX␈εβ]␈α⊗S␈α␈ho␈α␈w␈α
tha␈α␈t␈α∞p␈α␈rog␈α␈ram␈α
(4)␈α∞w␈α␈o␈α␈uld␈α
w␈α␈ork␈α
also␈α
if␈α∞th␈α␈e␈α∞in␈α␈struc␈α␈ti␈α↓o␈α␈n␈α
\␈↓ 
U␈εβ1␈↓ 
f␈εβ0␈↓ ≤␈εβ"
␈ββy␈↓ βY␈ε∃L␈α␈DX␈α∀=␈↓ ∧M␈ε∃=
␈ββ|␈↓ ↓H␈εβw␈α␈ere␈α
replac␈α␈ed␈αb␈α␈y␈α\␈↓ ∧@␈ε	c␈↓ ∧b␈εβ"␈α
f␈α↓o␈α␈r␈αcerta␈α␈i␈α↓n␈α
oth␈α␈er␈αcon␈α␈stan␈α}ts␈↓ λ
␈ε	c␈↓ λ↔␈εβ.
␈β∧0␈↓ ↓g␈ε∪6.␈↓ α␈εβ[␈ε	30␈↓ α;␈εβ]␈α⊗Discus␈α␈s␈αu␈α␈sing␈α
Meth␈α␈od␈α␈s␈α(1␈α␈a),␈α(1b),␈α(2a␈α␈)␈α↓,␈αan␈α␈d␈α(2␈α␈b)␈αwhe␈α␈n␈↓ λp␈ε	b␈↓ 	λ␈εβor␈↓ 	1␈ε	B␈↓ 	R␈εβi␈α↓s␈ε↔␈α␈␈εβ2.
␈β∧d␈↓ ↓g␈ε∪7.␈↓ α␈εβ[␈ε	M18␈↓ αX␈εβ]␈α⊗Giv␈α␈e␈α␈n␈α
tha␈α␈t␈α
0␈α
<␈↓ ∧p␈ε	␈↓ ¬∂␈ε↔∀␈↓ ¬=␈ε	x␈↓ ¬[␈ε↔∀␈↓ ε	␈ε	␈↓ ε$␈εβ+␈α	1/␈↓ εp␈ε	w␈↓ π⊗␈εβa␈α␈nd␈α
0␈ε↔␈α∀␈↓ λ$␈ε	u␈↓ λE␈ε↔∀␈↓ λs␈ε	w␈↓ 	␈εβ,␈α∞p␈α␈ro␈α␈v␈α}e␈α
that␈ε↔␈α
b␈↓ 
W␈ε	u␈↓ 
k␈ε	x␈↓ 
|␈ε↔c␈εβ␈α
is
␈β¬λ␈↓ π␈ε~␈␈εε1
␈β¬␈↓ ↓H␈εβe␈α␈qua␈α␈l␈α
to␈α	e␈α␈i␈α↓th␈α␈er␈ε↔␈α	b␈↓ β-␈ε	␈↓ β?␈ε	u␈↓ βS␈ε↔c␈εβ␈α
o␈α␈r␈ε↔␈α
b␈↓ ∧≡␈ε	␈↓ ∧0␈ε	u␈↓ ∧D␈ε↔c␈εβ␈α¬+␈α¬1.␈α
F␈α↓u␈α␈rthe␈α␈rmore␈ε↔␈α	b␈↓ εp␈ε	u␈↓ π∧␈ε	x␈↓ π∃␈ε↔c␈εβ␈α	=␈ε↔␈α
b␈↓ πc␈ε	␈↓ πu␈ε	u␈↓ λ	␈ε↔c␈εβ␈α	exa␈α␈ctly,␈α
if␈↓ 	9␈ε	u␈↓ 	W␈εβ<␈↓ 
↓␈ε	␈↓ 
∪␈ε	w␈↓ 
5␈εβand␈↓ 
t␈ε	
␈β¬3␈↓ ↓H␈εβis␈αan␈α
in␈α␈teg␈α␈er.
␈β¬d␈↓ βS␈ε∃M␈α␈IX
␈β¬g␈↓ ↓g␈ε∪8.␈↓ α␈εβ[␈ε	24␈↓ α;␈εβ]␈α⊗Wri␈α↓te␈α
a␈↓ ∧≠␈εβpro␈α␈gra␈α␈m␈α
ana␈α␈l␈α↓o␈α␈go␈α␈us␈α
to␈α
(1)␈α
tha␈α␈t␈αu␈α␈ses␈α
(5)␈α
an␈α␈d␈α
i␈α↓n␈α␈clud␈α␈es␈α
no␈α
d␈α␈ivision
␈βε∂␈↓ ↓H␈εβin␈α␈struct␈α␈i␈α↓o␈α␈ns.
␈βε?␈↓ εK␈εε34
␈βεC␈↓ ↓g␈ε∪9.␈↓ α␈εβ[␈ε	M27␈↓ αX␈εβ]␈α⊗Let␈↓ β5␈ε	u␈↓ βU␈εβb␈α␈e␈αa␈α␈n␈αin␈α␈t␈α␈eger,␈α0␈ε↔␈α
∀␈↓ ¬p␈ε	u␈↓ ε∂␈εβ<␈↓ ε:␈εβ2␈↓ εd␈εβ.␈α∞Assu␈α␈me␈αth␈α␈at␈αth␈α␈e␈αfo␈α␈l␈α↓lo␈α␈wing␈αseq␈α␈uen␈α␈ce␈αo␈α␈f
␈βεj␈↓ ↓H␈εβo␈α␈pera␈α␈tions␈α(e␈α␈quiv␈α␈alen␈α␈t␈αto␈α
add␈α␈iti␈α↓o␈α␈n␈αa␈α␈nd␈αb␈α␈ina␈α␈ry␈α\sh␈α␈ift-ri␈α↓g␈α␈h␈α␈t"␈αin␈α␈struc␈α␈ti␈α↓o␈α␈ns)␈αis␈αperfo␈α␈rmed␈α␈:
␈βπ5␈↓ 	%␈ε~␈␈εε␈α↓4
␈βπ7␈↓ βW␈εε1␈↓ εR␈εε1
␈βπ:␈↓ β↓␈ε	v␈↓ β≤␈ε↔ ␈α	b␈↓ βg␈ε	u␈↓ β{␈ε↔c␈εβ,␈↓ ¬;␈ε	v␈↓ ¬V␈ε↔ ␈↓ ε␈ε	v␈↓ ε→␈εβ+␈ε↔␈αλb␈↓ εc␈ε	v␈↓ εt␈ε↔c␈εβ,
␈βπ;␈↓ λ↓␈ε	v␈↓ λ≤␈ε↔ ␈↓ λF␈ε	v␈↓ λ←␈εβ+␈ε↔␈αλb␈↓ 	∃␈εβ2␈↓ 	K␈ε	v␈↓ 	]␈ε↔c␈εβ,
␈βπH␈↓ βW␈∧πHβWα
␈↓ εR␈∧πHεRα
␈βπJ␈↓ βW␈εε2␈↓ εR␈εε2
␈βπc␈↓ ∧&␈ε~␈␈εε8␈↓ ε←␈ε~␈␈εε16
␈βπf␈↓ λW␈εε1
␈βπi␈↓ β↓␈ε	v␈↓ β≤␈ε↔ ␈↓ βF␈ε	v␈↓ β←␈εβ+␈ε↔␈αλb␈↓ ∧∃␈εβ2␈↓ ∧K␈ε	v␈↓ ∧]␈ε↔c␈εβ,␈↓ ¬;␈ε	v␈↓ ¬V␈ε↔ ␈↓ ε␈ε	v␈↓ ε→␈εβ+␈ε↔␈αλb␈↓ εO␈εβ2␈↓ π∩␈ε	v␈↓ π#␈ε↔c␈εβ,␈↓ λ↓␈ε	v␈↓ λ≤␈ε↔ ␈α	b␈↓ λg␈ε	v␈↓ λy␈ε↔c␈εβ.
␈βπx␈↓ λW␈∧πxλWα
␈βπz␈↓ λW␈εε8
␈βλ7␈↓ ↓H␈εβPro␈α␈v␈α}e␈αtha␈α␈t␈↓ αl␈ε	v␈↓ βπ␈εβ=␈ε↔␈α	b␈↓ β>␈ε	u␈↓ βR␈εβ/10␈ε↔␈α␈c␈εβ␈αor␈ε↔␈αb␈↓ ∧R␈ε	u␈↓ ∧f␈εβ/1␈α␈0␈ε↔c␈απ␈␈εβ␈αλ1.
␈βλk␈↓ ↓V␈ε∪10.␈↓ α␈εβ[␈ε	22␈↓ α;␈εβ]␈α⊗The␈α	te␈α␈xt␈α	sho␈α}ws␈α
h␈α␈o␈α␈w␈α	a␈α	bin␈α␈ary␈α␈-cod␈α␈ed␈α	d␈α␈ecimal␈α	n␈α␈u␈α␈m␈α␈be␈α␈r␈α
c␈α␈an␈α	b␈α␈e␈α	dou␈α␈bled␈αλby␈α	u␈α␈sing
␈β	∪␈↓ ↓H␈εβv␈α␈ariou␈α␈s␈α
shifting,␈α∞ex␈α␈trac␈α␈ti␈α↓n␈α␈g,␈α∞an␈α␈d␈α
ad␈α␈dition␈α
o␈α␈pera␈α␈tions␈α
on␈αa␈α∞b␈α␈ina␈α␈ry␈α
com␈α␈pu␈α␈ter.␈α∩Gi␈α↓v␈α}e␈α
an
␈β	:␈↓ ↓H␈εβa␈α␈na␈α␈l␈α↓o␈α␈gou␈α␈s␈α∂meth␈α␈od␈α∞tha␈α␈t␈α∂comp␈α␈ute␈α␈s␈ε⊂␈α∂half␈↓ ε⊂␈εβof␈α∂a␈α∂b␈α␈i␈α↓n␈α␈ary␈α␈-cod␈α␈ed␈α∂d␈α␈ecima␈α␈l␈α⊂n␈α}um␈α}ber␈α∂(th␈α␈ro␈α␈wing
␈β	b␈↓ ↓H␈εβa␈α␈way␈αth␈α␈e␈αrem␈α␈aind␈α␈er␈αif␈αth␈α␈e␈αn␈α␈u␈α␈m␈α␈b␈α␈er␈αis␈αo␈α␈dd␈α␈).
␈β
⊗␈↓ ↓V␈ε∪11.␈↓ α␈εβ[␈ε	16␈↓ α;␈εβ]␈α⊗Con␈α}v␈α␈ert␈α(5␈α␈772␈α␈1␈↓ ∧:␈εβ)␈↓ ∧]␈εβto␈α
decima␈α␈l.
␈β
 ␈↓ ∧E␈εε8
␈β
F␈↓ ↓;␈ε↓x
␈β
J␈↓ ↓V␈ε∪12.␈↓ α␈εβ[␈ε	22␈↓ α;␈εβ]␈α⊗In␈α␈v␈α}en␈α␈t␈α
a␈α
r␈α␈apid␈α	pen␈α␈cil␈α↓-a␈α␈nd␈α␈-pap␈α␈er␈α
me␈α␈thod␈α	for␈α
co␈α␈n␈α␈v␈α}erting␈α
in␈α}tegers␈α
fro␈α␈m␈α
tern␈α␈ary
␈β
q␈↓ ↓H␈εβn␈α␈ota␈α␈ti␈α↓o␈α␈n␈αto␈α
d␈α␈ecima␈α␈l␈α↓,␈α
a␈α␈nd␈αil␈α↓lu␈α␈strate␈αy␈α␈o␈α␈ur␈αmeth␈α␈od␈αby␈αco␈α␈n␈α␈v␈α}erting␈α(121␈α␈201␈α␈12␈α␈102␈α␈10␈↓ 
P␈εβ)␈↓ 
t␈εβin␈α␈to
␈β
|␈↓ 
[␈εε3
␈β→␈↓ ↓H␈εβd␈α␈ecima␈α␈l␈α↓.␈αHo␈α␈w␈αw␈α␈ou␈α␈ld␈αy␈α␈o␈α␈u␈αgo␈α
from␈αd␈α␈ecimal␈αto␈αte␈α␈rna␈α␈ry?
␈βI␈↓ ↓;␈ε↓x
␈βJ␈↓ ¬$␈ε∃U␈↓ ε␈ε∃U␈↓ π1␈ε∃U
␈βM␈↓ ↓V␈ε∪13.␈↓ α␈εβ[␈ε	25␈↓ α;␈εβ]␈α⊗Assum␈α␈e␈α
tha␈α␈t␈α
l␈α↓o␈α␈cation␈α␈s␈↓ ¬?␈εβ+␈απ1␈α␈,␈↓ ε&␈εβ+␈αε2,␈↓ εq␈εβ.␈αε.␈αε.␈↓ π≡␈εβ,␈↓ πL␈εβ+␈↓ πt␈ε	m␈↓ λ≠␈εβco␈α␈n␈α␈tain␈α
a␈α	m␈α␈ultiple-p␈α␈recision
␈βq␈↓ πl␈ε∃MI␈α␈X␈↓ 	6␈ε∃M␈α␈IX
␈βt␈↓ ↓H␈εβfra␈α␈ction␈α
(.␈↓ αW␈ε	u␈↓ β⊂␈ε	u␈↓ βN␈εβ.␈αε.␈αε.␈↓ β{␈ε	u␈↓ ∧>␈εβ)␈↓ ∧T␈εβ,␈αwhe␈α␈re␈↓ ¬G␈ε	b␈↓ ¬↑␈εβi␈α↓s␈α
th␈α␈e␈α
w␈α␈ord␈α	si␈α↓z␈α␈e␈α
of␈↓ λ*␈εβ.␈αWrite␈α
a␈↓ 	}␈εβro␈α␈utine␈α	tha␈α␈t
␈β␈␈↓ αj␈ε~␈␈εε1␈↓ β#␈ε~␈␈εε2␈↓ ∧∞␈ε~␈␈↓ ∧'␈εm␈↓ ∧I␈εb
␈β≤␈↓ ↓H␈εβc␈α␈on␈α␈v␈α}erts␈α∂t␈α␈his␈α∂frac␈α␈ti␈α↓o␈α␈n␈α∞to␈α∂d␈α␈ecima␈α␈l␈α∂no␈α␈tation␈α␈,␈α⊂tru␈α␈nca␈α␈ti␈α↓n␈α␈g␈α∞i␈α↓t␈α∞to␈α∞180␈α∞d␈α␈ecimal␈α∂d␈α␈igits.␈α⊗The
␈βD␈↓ ↓H␈εβa␈α␈nsw␈α␈er␈αsh␈α␈ou␈α␈l␈α↓d␈αb␈α␈e␈αprin␈α}ted␈αon␈αt␈α␈w␈α␈o␈αl␈α↓in␈α␈es,␈α
with␈αth␈α␈e␈α
d␈α␈igits␈αgrou␈α␈pe␈α␈d␈αin␈α␈to␈α20␈αblock␈α␈s␈αof␈αnine
␈βh␈↓ ¬O␈ε∃CHAR
␈βk␈↓ ↓H␈εβe␈α␈ach␈α
sepa␈α␈rated␈α
by␈α
blan␈α␈ks.␈α(Use␈αthe␈↓ ε-␈εβi␈α↓n␈α␈stru␈α␈ction.)
␈β
≠␈↓ ↓;␈ε↓x
␈β
∨␈↓ ↓V␈ε∪14.␈↓ α␈εβ[␈ε	M27␈↓ αX␈εβ]␈α⊗(A.␈απSc␈α␈h␈↓ β↑␈εβ∪␈↓ β↑␈εβo␈↓ βo␈εβn␈α␈ha␈α␈ge.)␈α∞The␈αεtext␈α␈'␈α↓s␈απm␈α␈etho␈α␈d␈αεof␈απcon␈α}v␈α␈e␈α␈rti␈α↓n␈α␈g␈απm␈α}ultiple-pr␈α␈ecisi␈α↓o␈α␈n␈απin␈α}teger␈α␈s
␈β
C␈↓ ¬k␈εε2
␈β
G␈↓ ↓H␈εβre␈α␈quires␈αa␈α␈n␈αex␈α}ecu␈α␈ti␈α↓o␈α␈n␈αtime␈αof␈αor␈α␈der␈↓ ¬W␈ε	n␈↓ ε∧␈εβto␈αcon␈α␈v␈α}ert␈αan␈↓ πT␈ε	n␈↓ πh␈εβ-place␈αin␈α}teger,␈αwhen␈↓ 
~␈ε	n␈↓ 
;␈εβis␈αlarg␈α␈e.
␈β
n␈↓ ↓H␈εβS␈α␈ho␈α}w␈α⊂th␈α␈at␈α∂it␈α⊂is␈α∂po␈α␈ssi␈α↓b␈α␈le␈α∂to␈α∂con␈α}v␈α␈ert␈↓ ¬c␈ε	n␈↓ ¬w␈εβ-digit␈α∂de␈α␈cimal␈α∂i␈α↓n␈α}teger␈α␈s␈α⊂in␈α␈to␈α∂b␈α␈ina␈α␈ry␈α∂no␈α␈tation␈α∂in
␈β∞∪␈↓ ↓`␈εα(␈↓ βα␈εα)
␈β∞⊗␈↓ ↓H␈ε	O␈↓ ↓l␈ε	M␈↓ α∞␈εβ(␈↓ α→␈ε	n␈↓ α-␈εβ)␈↓ α>␈εβlog␈↓ αn␈ε	n␈↓ β≠␈εβcy␈α}cles,␈α
where␈↓ ∧g␈ε	M␈↓ ¬
␈εβ(␈↓ ¬∃␈ε	n␈↓ ¬)␈εβ)␈α
is␈α
a␈α␈n␈αup␈α␈per␈αbo␈α␈un␈α␈d␈α
o␈α␈n␈αthe␈αn␈α␈u␈α␈m␈α␈ber␈αof␈α
c␈α␈y␈α␈cles␈α
n␈α␈eed␈α␈ed
␈β∞=␈↓ ↓H␈εβto␈αm␈α}ultiply␈↓ αy␈ε	n␈↓ β
␈εβ-b␈α␈i␈α↓t␈αb␈α␈i␈α↓n␈α␈ary␈αn␈α}um␈α}bers␈αth␈α␈at␈αsatis|␈α␈es␈αthe␈α\sm␈α␈ooth␈α␈ne␈α␈ss␈α
c␈α␈on␈α␈dition"␈↓ 
"␈ε	M␈↓ 
E␈εβ(2␈↓ 
a␈ε	n␈↓ 
u␈εβ)␈ε↔␈α∃
␈β∞e␈↓ ↓H␈εβ2␈↓ ↓X␈ε	M␈↓ ↓{␈εβ(␈↓ αε␈ε	n␈↓ α~␈εβ).
␈β∂→␈↓ ↓V␈ε∪15.␈↓ α␈εβ[␈ε	M50␈↓ αX␈εβ]␈α⊗Ca␈α␈n␈αλth␈α␈e␈αλup␈α␈per␈αλb␈α␈ou␈α␈nd␈απon␈απthe␈αλtime␈αλto␈απcon␈α}v␈α␈ert␈αλlarg␈α␈e␈αλin␈α␈teg␈α␈ers,␈α	giv␈α}en␈αλin␈αλe␈α␈x␈α␈erc␈α␈i␈α↓se
␈β∂@␈↓ ↓H␈εβ1␈α␈4,␈αbe␈αsu␈α␈bsta␈α␈n␈α␈tially␈αlo␈α␈w␈α␈ere␈α␈d?␈α(Cf.␈αex␈α␈er␈α␈ci␈α↓s␈α␈e␈α4.3.3-12␈α␈.)
␈β∂t␈↓ ↓V␈ε∪16.␈↓ α␈εβ[␈ε	41␈↓ α;␈εβ]␈α⊗Con␈α␈struc␈α␈t␈αa␈αfast␈αline␈α␈ar␈αiterativ␈α}e␈αarra␈α␈y␈αfor␈αra␈α␈dix␈αc␈α␈on␈α␈v␈α}ersion␈αfrom␈αd␈α␈ecimal␈αto
␈β⊂≤␈↓ ↓H␈εβb␈α␈inar␈α␈y␈α(cf.␈αSect␈α␈i␈α↓o␈α␈n␈α4.3.3␈α␈)␈α↓.
␈β⊂P␈↓ ↓V␈ε∪17.␈↓ α␈εβ[␈ε	M40␈↓ αX␈εβ]␈α⊗Des␈α␈i␈α↓g␈α␈n␈αλ\id␈α␈eal"␈αλ⎇␈α␈oatin␈α␈g-po␈α␈in␈α␈t␈αλco␈α␈n␈α␈v␈α␈e␈α␈rsi␈α↓o␈α␈n␈αλsu␈α␈bro␈α␈utine␈α␈s,␈α	tak␈α␈i␈α↓n␈α␈g␈↓ 	W␈ε	p␈↓ 	h␈εβ-d␈α␈i␈α↓g␈α␈it␈αλdecima␈α␈l
␈β⊂w␈↓ ↓H␈εβn␈α}um␈α␈b␈α␈ers␈α
in␈α␈to␈↓ β∃␈ε	P␈↓ β-␈εβ-d␈α␈igit␈α∞b␈α␈inary␈αn␈α␈u␈α␈m␈α␈bers␈α
an␈α␈d␈α
v␈α␈i␈α↓ce␈α
v␈α}ersa,␈α∞in␈α
b␈α␈oth␈α
ca␈α␈ses␈α∞p␈α␈rod␈α␈uc␈α␈i␈α↓n␈α␈g␈α
a␈α
true
␈β⊃∨␈↓ ↓H␈εβro␈α␈un␈α␈ded␈α
resu␈α␈l␈α↓t␈αin␈α
the␈αsen␈α␈se␈αof␈αS␈α␈ection␈α
4.2.2.
␈β∪(

␈β↓Y␈↓ ↓H␈εα4.4␈ε∞␈↓ λ~R␈α↓A␈α␈DIX␈α	CONV␈α␈ERSION␈↓ 
v␈εα309
␈βα*␈↓ ↓V␈ε∪18.␈↓ α␈εβ[␈ε	H␈α↓M␈α␈39␈↓ αm␈εβ]␈α⊗(Dav␈α␈id␈αW.␈αM␈α␈atula␈α␈.␈α↓)␈α→Let␈↓ εβ␈εβrou␈α␈nd␈↓ εc␈εβ(␈↓ εn␈ε	u␈↓ πα␈εβ,␈↓ π⊃␈ε	p␈↓ π"␈εβ)␈αbe␈αth␈α␈e␈αfun␈α␈ction␈αo␈α␈f␈↓ 	H␈ε	b␈↓ 	V␈εβ,␈↓ 	j␈ε	u␈↓ 	}␈εβ,␈αa␈α␈nd␈↓ 
S␈ε	p␈↓ 
o␈εβtha␈α␈t
␈βα5␈↓ εX␈εb
␈βαR␈↓ ↓H␈εβre␈α␈prese␈α␈n␈α␈ts␈α∞the␈α∞be␈α␈st␈↓ βn␈ε	p␈↓ β␈␈εβ-d␈α␈i␈α↓g␈α␈i␈α↓t␈α∞ba␈α␈se␈↓ ¬(␈ε	b␈↓ ¬D␈εβ⎇o␈α␈ating␈α␈-poin␈α}t␈α∂ap␈α␈pro␈α}xima␈α␈ti␈α↓o␈α␈n␈α∞to␈↓ 	$␈ε	u␈↓ 	8␈εβ,␈α⊂in␈α∞the␈α∞sen␈α␈se␈α∂o␈α␈f
␈βαy␈↓ ↓H␈εβS␈α␈ection␈α∞4.2.2.␈α↔Und␈α␈er␈α∂th␈α␈e␈α∂assu␈α␈mptio␈α␈n␈α∂tha␈α␈t␈↓ εJ␈εβl␈α↓o␈α␈g␈↓ π␈ε	b␈↓ π(␈εβi␈α↓s␈α∂irra␈α␈ti␈α↓o␈α␈na␈α␈l␈α⊂a␈α␈nd␈α∞that␈α∂th␈α␈e␈α∂ran␈α␈ge␈α∂o␈α␈f
␈ββλ␈↓ εu␈εB
␈ββ!␈↓ ↓H␈εβe␈α␈xp␈α␈one␈α␈n␈α␈ts␈αis␈αun␈α␈l␈α↓imited␈α␈,␈αpro␈α␈v␈α}e␈αth␈α␈at
␈ββm␈↓ ε↔␈εα(␈↓ πz␈εα)
␈ββp␈↓ ∧o␈ε	u␈↓ ¬␈εβ=␈↓ ¬6␈εβrou␈α␈nd␈↓ ε#␈εβr␈α␈oun␈α␈d␈↓ π	␈εβ(␈↓ π∀␈ε	u␈↓ π(␈εβ,␈↓ π7␈ε	P␈↓ πO␈εβ),␈↓ πi␈ε	p
␈ββ{␈↓ ε␈εb␈↓ εx␈εB
␈β∧;␈↓ 	↔␈εp␈↓ 	%␈ε~␈␈εε1␈↓ 
␈εp
␈β∧?␈↓ ↓H␈εβh␈α␈olds␈α
for␈α
all␈↓ α␈␈ε	p␈↓ β⊂␈εβ-d␈α␈igit␈αb␈α␈ase␈↓ ∧1␈ε	b␈↓ ∧I␈εβ⎇␈α␈oatin␈α␈g-po␈α␈in␈α␈t␈α
n␈α␈u␈α␈m␈α␈bers␈↓ π≠␈ε	u␈↓ π9␈εβi␈α↓f␈α
an␈α␈d␈α
only␈α
if␈↓ 	↓␈ε	B␈↓ 	T␈ε↔∃␈↓ 	}␈ε	b␈↓ 
→␈εβ.␈α(␈α↓In␈α
o␈α␈the␈α␈r
␈β∧g␈↓ ↓H␈εβw␈α␈o␈α␈rds,␈α∞an␈α
\ide␈α␈al"␈α
i␈α↓n␈α␈pu␈α␈t␈α∞co␈α␈n␈α␈v␈α}ersion␈α
of␈↓ εα␈ε	u␈↓ ε#␈εβin␈α␈to␈α
an␈α
ind␈α␈epe␈α␈nd␈α␈en␈α␈t␈α
ba␈α␈se␈↓ 	%␈ε	B␈↓ 	;␈εβ,␈α∂fo␈α␈l␈α↓lo␈α␈w␈α␈ed␈α
b␈α␈y␈α
an
␈β¬∂␈↓ ↓H␈εβ\␈α␈i␈α↓d␈α␈ea␈α␈l␈α↓"␈α
ou␈α␈tpu␈α␈t␈α∞con␈α}v␈α␈e␈α␈rsi␈α↓o␈α␈n␈α∞o␈α␈f␈α∞this␈α∞re␈α␈sult,␈α∂will␈α∞alway␈α␈s␈α∞yield␈↓ λ,␈ε	u␈↓ λN␈εβag␈α␈ain␈α∞if␈α∞an␈α␈d␈α
on␈α␈l␈α↓y␈α
if␈α∞the
␈β¬6␈↓ ↓H␈εβin␈α}termed␈α␈iate␈αp␈α␈recision␈↓ ∧∀␈ε	P␈↓ ∧6␈εβi␈α↓s␈αsu␈α␈itably␈α
l␈α↓a␈α␈rge,␈αas␈αsp␈α␈eci|e␈α␈d␈αb␈α␈y␈αthe␈α
f␈α↓o␈α␈rm␈α␈u␈α␈l␈α↓a␈α
abo␈α}v␈α␈e.)
␈β¬i␈↓ ↓V␈ε∪19.␈↓ α␈εβ[␈ε	M23␈↓ αX␈εβ]␈α⊗Let␈αthe␈αd␈α␈ecimal␈αn␈α␈u␈α␈m␈α␈ber␈↓ ¬e␈ε	u␈↓ ε¬␈εβ=␈α(␈↓ ε=␈ε	u␈↓ εb␈εβ.␈αε.␈α¬.␈↓ π∞␈ε	u␈↓ π.␈ε	u␈↓ πN␈εβ)␈↓ π}␈εβbe␈αrep␈α␈resen␈α}ted␈αas␈αthe␈αb␈α␈i␈α↓n␈α␈ary␈α␈-
␈β¬s␈↓ εP␈εε7␈↓ π!␈εε1␈↓ πA␈εε0␈↓ πY␈εε1␈α␈0
␈βε⊂␈↓ ↓H␈εβc␈α␈ode␈α␈d␈α
de␈α␈cimal␈α
n␈α␈u␈α␈m␈α␈ber␈↓ ∧∨␈ε	U␈↓ ∧G␈εβ=␈α
(␈↓ ¬␈ε	u␈↓ ¬%␈εβ.␈αε.␈αε.␈↓ ¬R␈ε	u␈↓ ¬q␈ε	u␈↓ ε⊃␈εβ)␈↓ ε5␈εβ.␈α∩Fi␈α↓n␈α␈d␈α
ap␈α␈pro␈α␈priate␈α
c␈α␈ons␈α␈tan␈α␈ts␈↓ 	m␈ε	c␈↓ 
⊃␈εβa␈α␈nd␈α
m␈α␈ask␈α␈s
␈βε≠␈↓ ¬∪␈εε7␈↓ ¬e␈εε1␈↓ ε¬␈εε0␈↓ ε≤␈εε16␈↓ 	y␈εi
␈βε8␈↓ ↓H␈ε	m␈↓ ↓y␈εβso␈α
tha␈α␈t␈αth␈α␈e␈α
ope␈α␈ration␈↓ ∧5␈ε	U␈↓ ∧Y␈ε↔ ␈↓ ¬∧␈ε	U␈↓ ¬&␈ε↔␈␈↓ ¬M␈ε	c␈↓ ¬d␈εβ(␈↓ ¬o␈ε	U␈↓ ε⊃␈ε↔↑␈↓ ε0␈ε	m␈↓ εW␈εβ),␈αr␈α␈epea␈α␈ted␈α
for␈↓ λ/␈ε	i␈↓ λE␈εβ=␈α
1␈α␈,␈α2,␈α3␈α␈,␈αwi␈α↓ll␈α
con␈α␈v␈α}ert␈↓ ⊃␈ε	U
␈βεB␈↓ ↓d␈εi␈↓ ¬Y␈εi␈↓ εL␈εi
␈βε\␈↓ 
0␈ε∃AND
␈βε←␈↓ ↓H␈εβto␈α
t␈α␈he␈α
bin␈α␈ary␈α
re␈α␈prese␈α␈n␈α␈tatio␈α␈n␈α
of␈↓ ¬∂␈ε	u␈↓ ¬#␈εβ,␈αwh␈α␈ere␈α
\␈ε↔↑␈εβ"␈α
d␈α␈eno␈α␈tes␈α
extr␈α␈action␈α
(i.e.,␈α\lo␈α␈gical␈↓ 
n␈εβ"␈α
on
␈βππ␈↓ ↓H␈εβin␈α␈divid␈α␈ual␈αb␈α␈i␈α↓ts).
␈β∪(/FONT#1=cmathx[XGP,SYS]=↓⊗↔~xx/FONT#2=cmr10[XGP,SYS]=∂"'()+,-./0123456789:;<=ABCDEFGHIJKLMNOPRSTUWY[\]↑abcdefghijklmnopqrstuvwxyz{|⎇}}/FONT#3=cmr9[XGP,SYS]=∪"'()+,-./0123456789:;<=>?ABCDEFGHIJLMNOPRSTUWXY[\]abcdefghijklmnopqrstuvwxyz{|⎇⎇/FONT#4=cmr8[XGP,SYS]=0ACEFNORSTUU/FONT#5=cmr7[XGP,SYS]=+0123488/FONT#6=cmr6[XGP,SYS]=01234567899/FONT#8=cmi10[XGP,SYS]=BEFMUbdefkmnqruwxx/FONT#9=cmi9[XGP,SYS]=∂0123456789ABHJMOPUabcijmnpqruvwxyy/FONT#11=cmi7[XGP,SYS]=BEMbemnn/FONT#12=cmi6[XGP,SYS]=BJMbijmnpp/FONT#14=cmsc10[XGP,SYS]=ACDEHIMNORSTVXX/FONT#15=cms10[XGP,SYS]=∞∩∪≤-.:ACDEIJKMPSTWZ←abcdefghiklmnoprstuvwxyzz/FONT#16=cms9[XGP,SYS]=EGOabcdefhilmnoprtxyy/FONT#18=cmb10[XGP,SYS]=-.012345679ABCDEFHMST↑abcdefghilmnoprstuvxyy/FONT#19=cmb9[XGP,SYS]=.01234567899/FONT#21=cmtt[XGP,SYS]=+,-0125=ABCDEFHIJLMNOPRSTUVWXX/FONT#22=cmsy10[XGP,SYS]=↓α∂∀∃bcfg⎇⎇/FONT#23=cmsy9[XGP,SYS]=↓β∀∃ ↑bcfgjj/FONT#25=cmsy7[XGP,SYS]=/FONT#26=cmsy6[XGP,SYS]=/FONT#29=cmssb[XGP,SYS]=.14ACDEINORSTVXabell